Remove the nth node from the end of a singly linked list and return its head. For example, input: 1-2-3-4-5, and n = 2. Removing the second node from the end, the linked list becomes 1-2-3-5. You can assume the n will always be valid (less than the length of the linked list).
Two passes
The straightforward two-passes will be first to detect the length of the linked list and the second pass is to delete its n-th node. As the length of the linked list is no known without a pass, it would be difficult to know which node from the end to delete in the first place.
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) { int r = 0; auto p = head; // first pass - get the length while (head != NULL) { r ++; head = head->next; } // removing the head if (r == n) { p = p->next; return p; } head = p; // second pass, locate the node for (int i = 0; i < r - n - 1; i ++) { head = head->next; } // and delete it head->next = head->next->next; return p; // stored head } }; |
/**
* 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) {
int r = 0;
auto p = head;
// first pass - get the length
while (head != NULL) {
r ++;
head = head->next;
}
// removing the head
if (r == n) {
p = p->next;
return p;
}
head = p;
// second pass, locate the node
for (int i = 0; i < r - n - 1; i ++) {
head = head->next;
}
// and delete it
head->next = head->next->next;
return p; // stored head
}
};One pass
The trick of using One-pass is to have two pointers, fast and slow one. The slow pointer will only advance itself after n-th round, so when the fast pointer reaches the end, the slow pointer will be exactly n-th node from the end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { auto front = head, back = head; while (front) { front = front->next; if (n-- < 0) { back = back->next; } } if (n == 0) { head = head->next; } else { back->next = back->next->next; } return head; } }; |
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
auto front = head, back = head;
while (front) {
front = front->next;
if (n-- < 0) {
back = back->next;
}
}
if (n == 0) {
head = head->next;
} else {
back->next = back->next->next;
}
return head;
}
};The second method is obviously faster. Both methods need to make deleting-the-head a special case.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Break a Sentence into Words (Word Break Algorithms) - DFS, BFS and DP
Next Post: How to Reverse Linked List within Interval? (C/C++)
