19. 删除链表的倒数第 N 个结点

标签：LeetCode相关

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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

解题思路

指针，很神奇吧？

先不管它说的“一趟扫描”解决。删除的是“倒数”第n个节点。那么先获取整个链表的长度，这是肯定要有的。再看看倒数第n个是正数第几个。虽然这种我经常看到，但平时就是要想一会，作个图方便自己理解吧。

假设删除倒数第i个，那它左边就有length-i个元素。那被删除的节点从左边数起不就是第(length-i)+1个元素吗？它的前一个节点刚刚好就是链表的第length-i个节点。

接下来就是删节点。leetcode上面的链表题普遍开头的head节点都不为空，所以要删节点的话可以新建一个dummy节点。至于为什么新建这么个玩意….接下来解释。

删除节点的时候，有一种比较特殊的情况：链表中只有一个元素or删除的是头节点。这两个都需要你去操作链表的头节点。当然单独写个if语句作判断也可以。但是我们也可以往链表前面加一个dummy节点。这样“头节点”就变成了”链表中的某一个节点“，不管删除它还是其他什么的都是和链表中其他节点一样的操作，省的多写和多想。

不过最后要返回dummy-next。因为原先的head指针无论是地址还是值，都没有发生变化。所以无论你怎么返回head都是一开始ListNode* removeNthFromEnd(ListNode* head, int n)这里传进来的head地址。这个主要还是针对上面提到的“删除头节点”问题。

有点难理解？作个图先，我个人感觉链表图作图就很好理解了。如图所见，只要你没写释放（delete head）头节点的代码，那它就一直在内存中呆着。如果你没对头节点作操作，那dummy->next=head；如果删了头节点，那dummy->next=head->next。也就是说不管怎么样dummy->next始终是链表的头节点，那直接返回它就好了。

当然你也可以用几个if语句分别作判断，但我觉得代码还是简洁一点比较好。

ListNode*dummy=new ListNode(0,head);
end=dummy;
for(int i=1;i<=length-n+1;i++)
{     
     if(i==length-n+1)
     {
         end->next=end->next->next;
     }
     end=end->next;
}
return dummy->next;

完整代码（两次扫描）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*end=head;
        int length=1;
        while(end->next)
        {
            length++;
            end=end->next;
        }
        ListNode*dummy=new ListNode(0,head);
        end=dummy;
        for(int i=1;i<=length-n+1;i++)
        {
            
            if(i==length-n+1)
            {
                end->next=end->next->next;
            }
            end=end->next;
        }
        return dummy->next;
    }
};

接下来来看看双指针是怎么写的。

双指针，顾名思义用两个指针+一次扫描链表。为了方便删头节点，还是和上面一样，带上个dummy节点。

ListNode*dummy=new ListNode(0,head);
ListNode*first=head;
ListNode*second=dummy;

至于为什么first和second取这两个节点。依据的还是这张图。dummy相当于从length=0的地方开始算起。如果first指针先出发走i步，此时它距离该链表的最后一个节点还有length-i步（总和为length）。如果此时second指针和first指针再同时出发，都走length-i步。此时second指针指向链表尾部的null，而first指针刚刚好指向i节点的前一个节点。很神奇吧

完整代码（双指针）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       ListNode*dummy=new ListNode(0,head);
       ListNode*first=head;
       ListNode*second=dummy;
       for(int i=0;i<n;i++)
       {
           first=first->next;
       }
       while(first)
       {
           first=first->next;
           second=second->next;
       }
       second->next=second->next->next;
 
       return dummy->next;
    }
};