【小白爬Leetcode19】1.11 删除链表的倒数第N个节点 Remove Nth Node From End of List

Leetcode 19 $\color{#FF7D00}{medium}$medium

点击进入原题链接：LeetCode中国站

题目

Description

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

中文描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路一 用一个vector记录遍历到的每一个指针

如果不设置哑节点，需要考虑的情况有四种：

1. 删除的节点是最后一个，且链表长度大于1，直接让倒数第二个节点指向NULL；

2. 删除的节点是最后一个，且链表长度为1，那现在节点空了，直接返回NULL;

      if(n==1){//如果删除的是最后一个节点
         if(length-2>=0)  
         {
             l[length-2]->next = NULL;return head;
         }
         else{return NULL;}  // 考虑只有一个节点的情况
     }  

想了一下，第一种情况不是特殊情况，反正最后一个节点的->next = NULL,没必要多次一举，可以算在情况4里，所以上述代码改成了：

        if(n==1&&length==1){//如果删除的是最后一个节点
            return NULL;  // 考虑只有一个节点的情况
        }  

3. 删除的节点是第一个，那么直接返回head->next；

	 if(length-n==0){return head->next;}  //如果删除的是头节点

4. 最普通的，删除的节点是中间的某个，直接让前一个节点跳过当前节点，连接到下一个节点；

     else  //最普通的情况，删除中间节点
     {
         l[length-n-1]->next = l[length-n-1]->next->next;
         return head;
     }

完整代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> l;
        int length = 0;
        ListNode* cur = head;
        while(cur)
        {
            l.push_back(cur);
            length++;
            cur = cur->next;
        }
        //删除节点
        if(n==1&&length==1){//如果删除的是最后一个节点
            return NULL;  // 考虑只有一个节点的情况
        }  
        if(length-n==0){return head->next;}  //如果删除的是头节点
        else
        {
            l[length-n-1]->next = l[length-n-1]->next->next;
            return head;
        }
    }
};

由于用到了vector来记录链表的每一个指针，因此空间复杂度为O(n)
只遍历了一次，因此空间复杂度为O(n)

在第一遍OJ(Online Judgement)的时候，没考虑到情况2，出现了执行错误：

最后AC(accepted)，结果如下：

巧用哑节点

当然，这道题如果使用哑节点（为什么叫哑节点呢，因为这个节点是虚设的，最后是不会返回它的），情况会简化很多。
特殊情况无非是：

1. 链表只有一个节点：此时如果当作正常情况会出现vector下标length-n-1为-1的情况
2. 删除头节点：同样此时如果当作正常情况会出现vector下标length-n-1为-1的情况

那我设置一个头节点dummyHead，上述两种情况就都能避免vector下标length-n-1为-1的情况

修改后的代码如下：
注意，vector前面多加了一个dummyHead，但倒数第n个还是倒数第n个，它的下标依旧是 length-n-1，只要别忘了长度从1开始计算就行。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> l;
        int length = 1;
        ListNode dummyHead(0);
        l.push_back(&dummyHead);
        dummyHead.next = head;
        while(head)
        {
            l.push_back(head);
            length++;
            head = head->next;
        }
        //删除节点
        l[length-n-1]->next = l[length-n-1]->next->next;
        return dummyHead.next;
    }
};

思路二 两指针能做到的事，为什么要用vector？

$\color{#FF0000}{解题区看到这个思路，仿佛又回到了被快慢指针和Floyd算法秀智商的那天......}$解题区看到这个思路，仿佛又回到了被快慢指针和Floyd算法秀智商的那天......

直接放上官方解答：
上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 nn 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 nn 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

这里有一个要注意的点：first 和 second指针之间要 间隔 n 个节点，也就是说，first 指针 要比 second指针 走快n+1 步。为什么呢？因为删除第n个节点需要用到第n-1个节点的->next。所以 first 是 second 的前n+1个指针才能完成正常的删除节点操作。同样因为这一点，需要设一个dummyHead避免特殊情况。

完整代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummyHead(0);
        dummyHead.next = head;
        ListNode* first = &dummyHead;
        ListNode* second = &dummyHead;
        for(int i=0;i<n+1;i++)  // 让first比second先走n步
        {
            first = first->next;
        }
        while(first)
        {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return dummyHead.next;
    }
};

官方给出的是java的解答，我也一并放出来好了：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

AC后内存占用下去了一点。