19. Remove Nth Node From End of List

題意

給一個鏈表和一個數(shù)n, 刪掉倒數(shù)第n個數(shù).
比如給出1->2->3->4->5 和 2
返回 1->2->3->5
盡量保證只遍歷一次數(shù)組(one-pass)

解法:

常規(guī)思路是先完整遍歷一遍數(shù)組,得到數(shù)組的長度L.
然后再從頭遍歷一次, 刪除第L-n個數(shù).
但是這樣的做法不夠簡潔, 不符合one-pass的要求.

比較好的做法是通過快慢指針實現(xiàn).
快指針: 先從頭遍歷n個數(shù).
慢指針: 快指針遍歷完n個數(shù)后, 快指針距離鏈表尾部還剩L-n步, 如果此時慢指針與快指針同步遍歷, 那么就能實現(xiàn)慢指針遍歷L-n個位置.

坑:
鏈表為1->2, 刪除倒數(shù)第二個數(shù).
這種情況下, 快指針遍歷2步為NULL, 慢指針就始終指向1, 這樣就做不到刪除1這一項.
因為我們知道, 刪除第M項鏈表值, 需要將指針指向第M-1項.
解決這種問題的方法, 可以使用加一個空頭的方式, 即人為的把鏈表變?yōu)?br> 空->1->2, 然后同樣的從頭開始遍歷, 就能夠順利的跳出這個坑.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head)
            return head;

        ListNode *new_head = new ListNode(1);
        ListNode *fast = new_head, *slow = new_head;
        
        new_head->next = head;
        while (n--){
            fast = fast->next;
        }

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

        slow->next = slow->next->next;
        head = new_head->next;

        return head;
    }
};