Sword to Offer-22 链表中倒数第k个结点 ❀

09 Apr 2020 in Algorithm

• 题目描述：
  输入一个链表，输出该链表中倒数第k个结点。

解题思路：

1、设置一个指针p2从头开始先走k步，之后设置另一个指针p1从头开始与p2一起向后移动，那么当p2走到链表尽头为null的时候p1恰好指向倒数第k个结点;
2、注意考虑特殊情况，p2走完k步已经走出了链表，说明链表元素不足k个，无不存在倒数第k个结点，直接返回false。

问题图解：

AC代码：

// Find the Last k-th Number in Linklist

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        //p1指向表头，p2指向p1后面第k个元素
        while (p2!=null && k!=0) {
            p2 = p2.next;
            k--;
        }
        //p2还没有走k步就已经遍历完了链表，此时不存在倒数第k个结点
        if (k > 0) {
            return null;
        }
        //当p2走到表尾，p1就是倒数第k个元素
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

补充说明：

• 注意：若p2到链表最后一个结点就停下，往前数k个结点p1指向倒数第k+1个结点，所以需要等p2指向null时停止循环。

• 这里是牛客编码链接