0%

19. remove-nth-node-from-end-of-list

发表于 分类于

删除链表倒数第n个节点

题目

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

示例1：

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

思路

让快指针先行n步，即保持快慢指针的距离是n，那么慢指针指向的节点就是要删除的节点。

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* dummynode = new ListNode(-1);
        dummynode->next = head;
        ListNode* slow = dummynode;
        ListNode* fast = dummynode;
        while(n--&& fast!= NULL){
            fast = fast->next;
        }
        fast = fast->next;
        while(fast != NULL){
            fast = fast->next;
            slow = slow->next;
        }
        
        slow->next = slow->next->next;
        head = dummynode->next;
        return head;
    }
};