Problem Statement:
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Approach (Optimized Two-Pointer):
- Use a dummy node before the head to handle edge cases easily.
- Move the first pointer
nsteps ahead. - Move both first and second pointers until first reaches the end.
- Now second is just before the node to be deleted. Skip it using
second.next = second.next.next.
Time and Space Complexity:
- Time Complexity: O(n)
- Space Complexity: O(1)
var removeNthFromEnd = function(head, n) {
let sentinel = new ListNode(0, head);
let first = sentinel;
for (let i = 0; i < n; i++) {
first = first.next;
}
let second = sentinel;
while (first.next) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return sentinel.next;
};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode dummy = {0, head};
struct ListNode *first = &dummy, *second = &dummy;
for (int i = 0; i < n; i++) {
first = first->next;
}
while (first->next) {
first = first->next;
second = second->next;
}
struct ListNode* temp = second->next;
second->next = second->next->next;
free(temp);
return dummy.next;
}
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* sentinel = new ListNode(0, head);
ListNode* first = sentinel;
ListNode* second = sentinel;
for (int i = 0; i < n; ++i) first = first->next;
while (first->next) {
first = first->next;
second = second->next;
}
ListNode* toDelete = second->next;
second->next = second->next->next;
delete toDelete;
return sentinel->next;
}
};
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode first = sentinel;
ListNode second = sentinel;
for (int i = 0; i < n; i++) {
first = first.next;
}
while (first.next != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return sentinel.next;
}
}
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: Optional[ListNode]
:type n: int
:rtype: Optional[ListNode]
"""
sentinel = ListNode(0, head)
first = sentinel
# Move first pointer n steps ahead
for _ in range(n):
first = first.next
second = sentinel
# Move both until first reaches the end
while first.next:
first = first.next
second = second.next
# Delete the nth node from end
second.next = second.next.next
return sentinel.next
public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(0, head);
ListNode first = sentinel;
for (int i = 0; i < n; i++) {
first = first.next;
}
ListNode second = sentinel;
while (first.next != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return sentinel.next;
}
}
