LeetCode: Remove Nth Node From End of List

Posted on In Disqus:

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;
    }
};