Link to LeetCode Problem

S1: 双指针

• 定义快慢两个指针，从链表头部出发。
• 快指针先走 k 步，然后快慢指针同时同速前进。
• 当快指针走到链表尾部时，快指针走过的路程是 N 个节点（N 为链表长度），慢指针走过的路程是 N-k 个节点，所以慢指针刚好停在倒数第 k 个节点上。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (k-- > 0 && fast != NULL) {
            fast = fast->next;
        }
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

• Time: $O(N)$
• Space: $O(1)$