剑指offer:链表中倒数第K个结点(思路加答案)

链表中倒数第k个结点_牛客网

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路:

带头结点还是不带头结点的链表?不用纠结,随便确定一个,就以不带头结点为例。

  1. 首先想到的是用两个指针遍历链表。一个走的快遍历整个链表并统计出链表有多少个结点;另一个是达到一定条件开始遍历链表,当快指针遍历完整个链表的时候,慢指针刚好停在我们需要的倒数第K个。
  2. 那我们就需要确定几个条件,快指针是走到最后一个结点停下,还是走到最后一个结点后面的空结点停下?这将决定了我们的慢指针什么时候开始走。

答案:

以快指针走到null停下为例:
快指针停在null,慢指针刚好停在倒数第K个结点。
此时就它两的距离是K,所以我们设置慢指针开始走的条件应该是快指针走了K步之后。第K+1步的时候,快慢指针一起走。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        //初始化两个指针
        ListNode p,target;
        p = head;
        target = head;
        //用于统计快指针走的步数
        int i = 0;
        //当快指针指向null时,停止循环
        while(p != null){
            //当i大等k时,目标指针开始走
            /*这个判断写在最前面,逻辑会清晰点:
              不会漏掉对i=0时p、target都指向head时,target能不能走的判断*/
            if(i >= k){
                target = target.next;
            }
            //快指针指向下一个结点
            p = p.next;
            //i加一
            i++;
        }
        //如果i小于k,说明输入了k大于总结点数,返回null
        if(i < k){return null;}
        //否则返回目标结点
        return target;
    }
}

这道题还可以用栈、集合来解。

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务