[leetcode] 19. remove nth node from end of list

题目:

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

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.
Try to do this in one pass.

标签:

Linked List, Two Pointers

分析:

给定的是单列表,且要求解法为one-pass,因此可以使用两个指针同时移动,当前面的指针到达链表尾部时,删除后面指针指向的node即可。

代码:

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
31
32
33

struct {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == nullptr) return nullptr;
ListNode *a, *b;
a = b = head;
int i = 1;
while (i < n) {
// this should not happen
if (b->next == nullptr) break;
b = b->next;
}

ListNode* prev = nullptr;
while (b->next != nullptr) {
prev = a;
b = b->next;
a = a->next;
}

if (prev == nullptr)
head = head->next; // remove head
else
prev->next = a->next;
return head;
}
};