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

发表于 | 分类于 |
字数统计: 189 | 阅读时长 ≈ 1

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

题面

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

解法

利用快慢指针，先将fast指针向前移动n个结点，再快慢指针同时移动
当快指针到达链表尾时，慢指针刚好指向倒数第n个结点
利用dummy指针可以规避删除第一个结点的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        ListNode* dummy = new ListNode(0, head);
        ListNode* slow = dummy, *fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast -> next;
        }
        while(fast != nullptr) {
            fast = fast -> next;
            if (fast == nullptr) {
                slow -> next = slow -> next -> next;
                break;
            }
            else {  
                slow = slow -> next;
            }
        }
        return dummy -> next;
    }
};