[Leet Code] Two Pointers (투포인터): 19.Remove Nth Node From End of List - Medium

문제 / 코드

 

Description

Remove the nth node from the end of the list and return its head.

 

How to solve

Since the given linked list can only be traversed from the first to the last node, we need to find a way to calculate where nth node from the end is from the start.
However, the length of a linked list is not fixed, how can we find it?

 

Let the length of the given linked list be l. Then the position of the target node is l-n.

What we need to know is the position from the start, but l-n expresses the position from the end.

So let the position from the start be a variable x, then we can say x = l-(l-n).

Now we can find x with two pointers.

 

1. Initialize two pointers to point the first node of the given list.
2. Move one pointer(Let's call this pointer "fast pointer") n nodes. The other one is still points the first node.
   • Be aware that the pointer is starting from 1st node, not 0. That means if a pointer moves n nodes, it'll point n+1th node, not nth node.
3. Once Fast pointer points nth node from the start, there are 2 cases:
   • Fast pointer points the next of the last node of the linked list (=None):
     This case means n = length of the linked list. That means we need to remove the first node. The answer of this problem is head.next
   • Still left nodes to go
     start to move the other pointer (let's call this pointer to "slow pointer"). Also keep moving Fast pointer.
4. Once Fast pointer points the last node of the list, Slow pointer is poiting n+1th node from the end.
   • At step 2, Fast pointer moved n+1 nodes because it start from 1 and moved n nodes.
   • At step 3, Fast pointer and Slow pointer moved as many nodes remained after Fast pointer moved n+1 nodes at step 2. That means l-(n+1).
   • Therefore, the next node of the node Slow pointer is pointing is nth node from the end.
5. Replace the next node of the node slow node is pointing to the next next node Slow pointer is pointing and return head

 

Pseudo Code

fast, slow = head

for _ in range(n):
    fast = fast.next

if not fast: # n = length of the given list
    return head.next

while fast.next: # until fast pointer points the last node
    fast = fast.next # Fast pointer keep moving
    slow = slow.next # Slow pointer starts to move

# Now Slow pointer is pointing n+1th node from the end
slow.next = slow.next.next
return head