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

题目描述

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

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

示例 1：

img

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

这道题的思路比较简单。运用快慢两个指针，快指针先走n步，然后慢指针和快指针同步走，当快指针走到结尾的时候，慢指针指向的位置就是要删除的结点。

这个题有两个问题：

  1. 要删除当前结点，那么就需要记录当前结点的上一个结点；
  2. 如果要删除的结点是头结点，那么就需要特判。

但是这两个问题我们可以通过设置虚拟头结点virtualHead来解决，让virtualHead的next指针指向头结点。这样就会统一删除操作，不用进行特判。

示例代码如下。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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) {}
};

ListNode* removeNthFromEnd(ListNode* head, int n)
{
    ListNode *virtualHead=new ListNode();
    virtualHead->next=head;

    ListNode* pre=virtualHead;
    ListNode* cur=head;
    ListNode* tail=head;

    while(n--)
    {
        tail=tail->next;
    }
    while(tail)
    {
        tail=tail->next;
        cur=cur->next;
        pre=pre->next;
    }

    pre->next=cur->next;
    return virtualHead->next;
}