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

Question

题目

输入一个链表，输出该链表中倒数第 k 个结点。

解析

两种思路，一种常规思路，一种双指针。

1、常规思路

• 先遍历一遍求出链表长度 len ；
• 然后再从头开始走 len - k 个就可以到倒数 k 个结点；

代码:

public class Solution {
    //常规解法
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        if (k > len)
            return null;
        cur = head;
        for (int i = 0; i < len - k; i++)
            cur = cur.next;
        return cur;
    }
}

2、双指针

• 设置两个指针一开始都指向 head ；
• 然后先让第一个指针 first 走 k-1 步，然后两个指针再一起走，当第二个指针 second 走到末尾( second.next = null ) 时，第一个指针 first 就刚好指向倒数第 k 个结点；
• 具体长度关系推一下就清楚了；

代码:

public class Solution {

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0) //注意要特判
            return null;
        ListNode fi = head, se = head;
        for (int i = 1; i <= k - 1; i++) // first 先走 k-1 步
            fi = fi.next;
        if (fi == null) //k > len 特判
            return null;
        while (fi.next != null) { // 注意是 fi.next != null
            fi = fi.next;
            se = se.next;
        }
        return se;
    }
}