计算机科学基础leetcode刷题链表
,
Source
Edit
History

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

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

思路

双指针法,fast指针先slow走n+1步,再让他们同时移动,这样当fast指向nullptr的时候slow指向倒数第n个节点的前一个

需要注意，一定要用一个虚拟头节点作为头节点，这样只有一个节点时才可以返回的了空节点。

复杂度

  • 时间复杂度:

$O(n)$

  • 空间复杂度:

$O(1)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0),*slow = dummyHead,*fast = dummyHead;
        dummyHead->next = head;
        //fast先走n步
        while(n-- && fast != nullptr) {
            fast = fast->next;
        }
        //再多走一步
        fast = fast->next; 
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        //删除
        slow->next = slow->next->next; 
        return dummyHead->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

class Solution {

public:

    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
  
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
  
        n++;
        while(n-- && fast != nullptr) {
            fast = fast->next;
        }

        while(fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        ListNode* p = slow->next;
        slow->next = slow->next->next;
        delete p;
  
        return dummyHead->next;
    }
};