0%

LeetCode: Remove Nth Node From End of List

https://leetcode.com/problems/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.

解题要点

  1. 设两个指针,间隔n,后面的指针p2->next为NULL时,前面的指针p1->next就是要删除的节点。
  2. 考虑到需要删除头节点的情况(传入[1],1或[1,2],2),需要给其加个临时头,并且在用完后delete这个临时节点。

CODE

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == nullptr) return nullptr;
ListNode *ph = new ListNode(-1);
ph->next = head;
ListNode *p1, *p2;
p1 = p2 = ph;
for (int i = 0; i < n; ++i) p2 = p2->next;
for (; p2 != nullptr; p1 = p1->next, p2 = p2->next)
{
if (p2->next == nullptr)
{
ListNode *tmp = p1->next;
p1->next = p1->next->next;
delete tmp;
break;
}
}
p1 = ph;
ph = ph->next;
delete p1;
return ph;
}
};