19.删除链表的倒数第N个元素

发表于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

给你一个链表，删除链表的倒数第N个结点并返回链链表的头结点。利用双指针中的快慢指针解决问题。

【题目】

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

分析：

对于链表而言，访问特定下标的元素是很困难的。

我们做过三个相关的题目：

1、设计链表：在特定的位置插入元素，特定的正向位置删除元素，这需要我们从虚拟头结点开始进行遍历。

2、删除链表的中间节点：这时候我们并不知道应该删除的是哪一个下标，我们通过遍历得到链表的长度也不是现实的，所以我们可以选择利用指针移动之间的倍数关系来实现。即：双指针中的快慢指针，快指针一次走两个格，慢指针一次走一个格，当快指针走到头的时候，慢指针刚好走到了中央的位置。

3、就是我们要删除倒数的元素了，我们可以让快的节点超过慢节点n个元素，当快节点到头的时候，慢节点刚好指向了倒数第n个元素。但需要注意的是，我们希望进行删除操作，所以我们需要在操作第N个元素的前一个节点，所以，判断关系很重要。

【解答】

双指针-快慢双指针法

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
/**
 * 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* prev = new ListNode(0);
        prev -> next = head;
        ListNode* slow = prev;
        ListNode* fast = prev;
        while (n--) {
            fast = fast -> next;
            if (fast == nullptr) {
                return prev -> next;
            }
        }
        while (fast -> next != nullptr) { // 要删掉的节点的前一个节点
            fast = fast -> next;
            slow = slow -> next;
        }
        slow -> next = slow -> next -> next;
        return prev ->next;
    }
};