Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Constraints:
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
Examples:
Input: [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: We remove the second node from the end which is node with value 4.
Solutions
Two Pointers
Time: O(L)Space: O(1)
We use two pointers, first and second, both starting at the head of the list. We move the first pointer n steps ahead. Then we move both pointers one step at a time until the first pointer reaches the end of the list. At this point, the second pointer is at the node right before the nth node from the end. We then remove the nth node from the end by changing the next pointer of the second pointer.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* first = dummy;
ListNode* second = dummy;
for (int i = 0;
i <= n;
i++) {
first = first->next;
}
while (first) {
first = first->next;
second = second->next;
}
second->next = second->next->next;
return dummy->next;
}
}
;Follow-up:
How would you handle the case where the list is empty?
