Remove Nth Node From End of List
franklinqin0 Linked ListTwo Pointers
# Definition for Singly-Linked List
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
1
2
3
4
2
3
4
# Solution
# Two Pointers
Use a dummy node and keep a hi pointer n nodes ahead of a lo pointer, then move both together until hi reaches the end, so lo lands just before the node to remove.
Complexity
time:
space:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(next=head)
# `hi` walks n steps
cnt = 0
hi = dummy
while cnt < n:
cnt += 1
hi = hi.next
# `lo` arrives at (n+1)-th node from the end
lo = dummy
while hi.next:
lo = lo.next
hi = hi.next
lo.next = lo.next.next
return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17