[LeetCode] 19. Remove Nth Node From End of List

佚名 4年前 (2020-02-16) 算法 558人围观抢沙发百度已收录

1. 原题链接：https://leetcode.com/problems/remove-nth-node-from-end-of-list/

2. 解题思路

利用哑节点将边界case转化为一般case
倒数第n个，也就是顺数第(链表总长度-n+1)个
由于需要删除顺数第(总长度-n+1)个，因此需要知道顺数第(总长度-n)个节点的位置，该位置可以通过快慢指针得到

3. 算法

创建包含哑节点的链表，这样可以避免处理删除头结点和只有一个节点的这两种情况
fast指针先移动n步，然后fast和slow指针同时移动，一直到fast指针指向最后一个节点时，slow指针刚好指向第(总长度-n)个节点
现在slow指针的下一个节点就是需要删除的节点

4. 实现

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(-1);
        dummy.next = head;
        
        ListNode *fast = &dummy;
        ListNode *slow = &dummy;
        for(int i = 0; i < n; i++){ //移动[n]步
            fast = fast->next;
        }
        
        while(fast->next != NULL){ //移动[链表长度-n]步
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy.next;
    }
};