题解 | 链表中倒数最后k个结点

解法一、双指针

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode head, int k) {
        if (head == null || k < 0)
            return null;
        ListNode first = head;
        ListNode last = head;

        for(int i = 0; i < k; i++) { // 第一个指针先向前走k步
            if(first == null) 
                return null; // k超过了链表的长度
            first = first.next;
        }
        while(first != null) { // 两个指针一起走
            first = first.next;
            last = last.next;
        }
        return last;
    }
}

解法二、递归

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode head, int k) {
        if (head == null || k == 0)
            return null;
        int[] count = new int[1];
        ListNode ret = rec(head, count, k);
        if (count[0] < k)
            return null;
        else 
            return ret;
    }
    // 递归辅助函数
    private ListNode rec(ListNode head, int[] count, int k) {
        if (head == null) {
            count[0] = 0;
            return null;
        }
        ListNode x = rec(head.next, count, k);
        if (k == count[0]) { 
            return x; // 找到了倒数第k个元素
        } else {
            count[0]++;
            return head;
        }
    }
}

解法三、栈

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode head, int k) {
        if (head == null || k <0)
            return null;
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        if (k > stack.size())
            return null;
        ListNode ret = null;
        for (int i = 0; i < k; i++) {
            ret = stack.pop();
        }
        return ret;
    }
}