描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

• 要求：空间复杂度 O(n)，时间复杂度 O(n)
• 进阶：空间复杂度 O(1)，时间复杂度 O(n)

类似题目：删除链表的倒数第n个节点

思路1：列表存储，取出倒数第k个节点

使用列表存储每个节点，取出倒数第K个节点。空间复杂度O(n)

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
         if(pHead == null) {
             return null;
         }
         ArrayList<ListNode> list = new ArrayList<ListNode>();
         while(pHead != null) {
             list.add(pHead);
             pHead = pHead.next;
         }
         if(k > list.size() || k == 0){
             return null;
         }
         return list.get(list.size() - k);
    }
}

思路2：统计链表长度，再次遍历

遍历统计链表长度n，再走n-k步

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int n = 0;
        ListNode p = pHead;
        while(p != null) {
            n++;
            p = p.next;
        }
        p = pHead;
        while(p != null) {
            if(n == k){
                return p;
            }
            p = p.next;
            n--;
        }
        return null;
    }
}

思路3：递归

出栈的时候倒数

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        i = k;
        recur(pHead);
        return ret;
    }
    ListNode ret;
    int i;
    void recur(ListNode node) {
        if(node == null) {
            return;
        }
        recur(node.next);
        i--;
        if(i == 0){
            ret = node;
            return;
        }
    }
}

思路4：快慢指针

假设链表长度为n，快指针先走k步，慢指针再开始，当快指针到达终点n时，慢指针走了n-k步，即倒数第k个节点

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        for(int i = 0; i < k; i++){
            if(fast == null) {
                return null;
            }
            fast = fast.next;
        }
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}