MediumBlind75Linked ListTwo Pointers
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.
Examples
Input
head = [1,2,3,4,5], n = 2
Output
[1,2,3,5]
The 2nd node from the end is 4. Remove it.
Input
head = [1], n = 1
Output
[]
The only node is removed.
Constraints
- •
The number of nodes in the list is sz - •
1 <= sz <= 30 - •
0 <= Node.val <= 100 - •
1 <= n <= sz
Approaches
First pass: count the length. Second pass: remove the (length-n+1)th node.
CodeT: O(L) | S: O(1)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_nth_from_end(head, n):
length = 0
curr = head
while curr:
length += 1
curr = curr.next
if length == n:
return head.next
curr = head
for _ in range(length - n - 1):
curr = curr.next
curr.next = curr.next.next
return headUse two pointers with a gap of n.
CodeT: O(L) | S: O(1)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextUse a dummy node to handle edge cases.
Diagram
1->2->3->4->5, n=2
dummy->1->2->3->4->5
fast advances 3 steps: at node 3
slow at dummy
Move both: fast at None, slow at 3
Remove 4: 1->2->3->5
CodeT: O(L) | S: O(1)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Two Pass - Count Length | O(L) | O(1) | First pass: count the length. Second pass: remove the (length-n+1)th node. |
| Two Pointers - One Pass | O(L) | O(1) | Use two pointers with a gap of n. |
| Optimized with Dummy Node | O(L) | O(1) | Use a dummy node to handle edge cases. |
Two Pass - Count Length
T: O(L)S: O(1)
First pass: count the length. Second pass: remove the (length-n+1)th node.
Two Pointers - One Pass
T: O(L)S: O(1)
Use two pointers with a gap of n.
Optimized with Dummy Node
T: O(L)S: O(1)
Use a dummy node to handle edge cases.
Common Mistakes
Not using a dummy node to handle head removal edge case
Advancing the fast pointer n steps instead of n+1
Forgetting to return dummy.next instead of head