Leetcode题解剑指 Offer 22. 链表中倒数第k个节点

PROBLEM

难度简单

MY ANSWER

首先遍历一次得出链表长度，然后再遍历一次返回链表。时间复杂度O(n)，空间复杂度O(1)。

/**
 * 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) {
        int cnt = 0;
        ListNode* tmp = head;
        while(tmp) {
            tmp = tmp->next;
            cnt++;
        }
        tmp = head;
        for(int i = 0; i < cnt - k; i++) {
            tmp = tmp->next;
        }
        return tmp;
    }
};

BETTER ANSWER

快慢指针，快指针比慢指针先走k步，然后开始一起走直到快指针到达末尾，慢指针即为答案。时间空间复杂度与上面的一个阶，但比上面要低。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* fast = head;
        ListNode* slow = head;

        while (fast && k > 0) {
            fast = fast->next;
            k--;
        }
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

SUMMARY

注意使用双指针来获取倒数节点，避免重复遍历。