【刷穿 LeetCode】剑指 Offer 22. 链表中倒数第k个节点 :「栈/队列」&「差值法」&「快慢指针」

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
复制代码

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while (head != null) {
            d.addLast(head);
            head = head.next;
        }
        ListNode ans = null;
        while (k-- > 0) ans = d.pollLast();
        return ans;
    }
}
复制代码

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Deque<ListNode> d = new ArrayDeque<>();
        while (head != null) {
            d.addLast(head);
            head = head.next;
        }
        k = d.size() - k + 1;
        ListNode ans = null;
        while (k-- > 0) ans = d.pollFirst();
        return ans;
    }
}
复制代码

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int cnt = 0;
        ListNode tmp = head;
        while (tmp != null && ++cnt > 0) tmp = tmp.next;
        cnt -= k;
        while (cnt-- > 0) head = head.next;
        return head; 
    }
}
复制代码

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (k-- > 0) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
复制代码