0%

[Leetcode]19. Remove Nth Node From End of List(C++)

题目描述

题目链接:19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

例子

例子 1

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

例子 2

Input: head = [1], n = 1
Output: []

例子 3

Input: head = [1,2], n = 1
Output: [1]

Constraints

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

解题思路

要求删除链表中倒数第 n 个节点,直观的思路是遍历一次链表获取长度 l,再遍历一次将第 l-n 个节点删掉即可。不过题目要求只遍历一次,所以可以用快慢指针的方法,让其直接相隔 n 个节点,这样当快指针到末尾时慢指针会指向第 l-n-1 个节点,将下一个节点删除即可。

代码如下:

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
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
int step = 0;
while (step < n) {
fast = fast->next;
step++;
}

if (!fast) return head->next;

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

slow->next = slow->next->next;

return dummy->next;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 19.RemoveNthNodeFromEndOfList.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions