[LeetCode]19. Remove Nth Node Fr

19. Remove Nth Node From End of List

题意

给一个链表和一个数n, 删掉倒数第n个数.
比如给出1->2->3->4->5 和 2
返回 1->2->3->5
尽量保证只遍历一次数组(one-pass)

解法:

常规思路是先完整遍历一遍数组,得到数组的长度L.
然后再从头遍历一次, 删除第L-n个数.
但是这样的做法不够简洁, 不符合one-pass的要求.

比较好的做法是通过快慢指针实现.
快指针: 先从头遍历n个数.
慢指针: 快指针遍历完n个数后, 快指针距离链表尾部还剩L-n步, 如果此时慢指针与快指针同步遍历, 那么就能实现慢指针遍历L-n个位置.

坑:
链表为1->2, 删除倒数第二个数.
这种情况下, 快指针遍历2步为NULL, 慢指针就始终指向1, 这样就做不到删除1这一项.
因为我们知道, 删除第M项链表值, 需要将指针指向第M-1项.
解决这种问题的方法, 可以使用加一个空头的方式, 即人为的把链表变为
空->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;
    }
};