心之所向便是光

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

  • 2021-05-24
  • 作者 Ender
  • 2.08K 字
  • 次阅读

题目描述：

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

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

示例 1：

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

链接：

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

题目分析

  最简单的办法当然是先对链表进行一次遍历得到长度，然后再得到需要删除的结点位置，第二次遍历到该位置并进行删除，如此一共需要进行两趟扫描。但是如果我们采用前后双指针的做法，让前指针先走 $n$ 步，之后两个指针再一起前进，则当前指针到达链表末尾的时候，后指针就到了需要删除的位置，这样只进行一趟扫描就可以解决问题。
  由于删除链表结点的操作是令前置结点的 next 指向其后置结点，则实际上我们搜索到删除结点的前置结点就停下更方便删除，因此循环退出条件也变为前指针的 next 是否已经指向空而不是前指针本身为空。
  注意到，如果 $n$ 的值等于链表长度，也即需要删除的结点是头结点时，头结点没有前置结点，则直接返回头结点的后置结点即可。而这种情况下前指针走了 $n$ 步刚好为空，可以作为判断的条件。
  PS：代码中含有的注释部分是另一种写法，包括了释放删除结点的内存。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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 *front = head;
        // 前指针先走 n 步
        for(int i = 0; i < n; i++){
            front = front->next;
        }

        // 需要删除的是头结点
        /*
        if(front == nullptr){
            ListNode *res = head->next;
            delete(head);
            return res;
        }
        */
        if(front == nullptr) return head->next;

        ListNode *behind = head;
        // 前后指针一起走
        while(front->next != nullptr){
            front = front->next;
            behind = behind->next;
        }
        /*
        ListNode *del = behind->next;
        behind->next = del->next;
        delete(del);
        */
        behind->next = behind->next->next;
        return head;
    }
};

  时间复杂度：$O(L)$，其中 $L$ 是链表的长度。我们总共对链表进行了一次遍历。
  空间复杂度：$O(1)$。只需要常数个指针进行遍历即可。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-09