清风的技术小屋

不为所动, 做更专业的自己

0%

LeetCode 19 - Remove Nth Node From End of List

问题描述

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

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Related Topics: Linked List, Two Pointers

原问题: 19. Remove Nth Node From End of List

中文翻译版: 19. 删除链表的倒数第N个节点

解决方案

这道题可以使用双指针方法解决,设定两个指针 p1p2,先让指针 p1 遍历 n 个节点,然后指针 p2 开始和指针 p1 同步遍历链表,当指针 p1 遍历完链表后,指针 p2 刚好指向倒数第 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
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == NULL)
return NULL;

ListNode *pos1, *pos2, *prev;
int step;

prev = NULL;
pos1 = pos2 = head;
step = 0;
while (pos2 != NULL) {
pos2 = pos2->next;
step += 1;
if (step > n) {
prev = pos1;
pos1 = pos1->next;
}
}
if (prev == NULL)
head = head->next;
else
prev->next = pos1->next;

return head;
}
};