搜索内容

有一个问题?

如果您有任何疑问,可以在下面询问或输入您要寻找的!

剑指offer22-链表中倒数第k个结点

生成海报
Java硬件工程师
Java硬件工程师 2021-02-09 20:49
阅读需:0

题中来源于:挥剑 Offer 22. 链表中倒数第k个连接点

1.难题叙述:

键入一个链表,輸出该链表中倒数第k个连接点。为了更好地合乎大部分人的习惯性,题中从1逐渐记数,即链表的尾连接点是倒数第一个连接点。

比如,一个链表有 6 个连接点,从头开始连接点逐渐,他们的值先后是 1、2、3、4、5、6。这一链表的倒数第 2 个连接点是数值 4 的连接点。

实例:

给出一个链表: 1->2->3->4->5, 和 k = 2.

回到链表 4->5.

2.题解:

2.1.解析xml链表法解题思路:

解析xml一遍链表,能够获得链表的长短,随后用链表的长短length-k+1=倒数第k个节点所属的部位
留意,相关链表的题型最好是设定一个头节点,头节点没有一切数据信息,即卫兵节点,那样便捷计算的完成,也容易中后期再寻找全部链表,头节点是不可以改的,这是一个习惯性

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null){
            return null;        //假如链表头为空,回到空
        }
        ListNode realHead=new ListNode(-1);        //建立头节点
        realHead.next=head;             //让建立的头节点偏向题中所给的链表头
        ListNode p=realHead.next;
        int length=0;
        //测算链表的长短
        while(p!=null){
            length++;
            p=p.next;
        }
        //测算倒数第k个节点的部位
        int index=length-k+1;
        if(index<0){
            return null;        //这时k不法
        }
        p=realHead;         //p再度解析xml
        System.out.println(index);
        for(int i=0;i
            p=p.next;
        }
        return p;
    }
}

在这里插入图片描述

2.2.双指针法解题思路:

应用双指针则能够无需统计分析链表长短。
结构卫兵头节点及其双指针:结构卫兵头节点,及其前表针q和后表针p 。
搭建双指针间距: 前表针 q先往前走 k 步(完毕后,双指针p 和 q间距离 k 步)。
双指针一同挪动: 循环系统中,双指针 p和 q每场都往前走一步,直到 q踏过链表 尾连接点 时跳出来(跳出来后, p与尾连接点间距为 k-1,即 p偏向倒数第 k 个连接点)。
传参: 回到 p就可以。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode realHead=new ListNode(-1);         //结构头节点
        realHead.next=head;
        ListNode p=realHead;                //后表针
        ListNode q=realHead;                //前表针
        for(int i=0;i               //前表针后退k位
            if(q==null){
                return null;
            }
            q=q.next;
        }
        while(q!=null){                     //前表针和后表针另外后退
            p=p.next;
            q=q.next;
        }
        return p;           //回到后表针就可以

    }
}

在这里插入图片描述

评论
  • 消灭零回复