[Two Pointers] Remove Nth Node from End of List

 Remove Nth Node from End of List Problem

Statement

Given a singly linked list, remove the n^th node from the end of the list and return its head.

Constraints

• The number of nodes in the list is k.
• 1≤1≤ k ≤10^3
• −10^3≤ Node.data ≤10^3
• 1≤ n ≤ k

Approaches

1. Set two pointers, right and left, at the head of the linked list.

2. Move the right pointer n steps forward.

3. Move both the right and left pointers forward until the right pointer reaches the last node. At this point, the left pointer will be pointing to the node behind the nth last node.

4. Relink the left node to the node next to left's next node.

5. Return the head of the linked list.

 

1. Naive approach  requires two traversals of the linked list: one to calculate the length and another to locate and remove the target node.

   1) Traverse the entire linked list to calculate its length,L.

   2) Compute the position of the node to be removed from the start of the linked list: L - n + 1

   3) Start from the head and traverse the linked list until you reach the (L - n)-th node, which is the node just before the target node.

   4) Remove the node: 

      - Save the next node of the current node in a temporary pointer.

      - Relink the current node to skip over the target node by pointing its next to the node after the target node.

      - Delete the target node.

2. Optimized approach using two pointers

It removes the nth node from the end of a linked list in one traversal by maintaining a fixed gap between two pointers. Initially, both left and right pointers start at the head, and the right pointer is moved forward by n steps, creating a gap of n nodes. This gap ensures that when the right pointer reaches the end of the list, the left pointer is positioned just before the node to be removed. Both pointers then move forward together, maintaining the gap, until the right pointer reaches the end. At this point, the target node is skipped by updating the left pointer's next link. If the right pointer reaches the end during the initial n steps, it indicates the head node is the target, which is removed by returning the next node of the head. 

   1) Initalize two pointers, left and right, both pointing to the head of the linked list.

   2) Move the right pointer n steps ahead. This creates a gap of n nodes between the left and right pointers.

   3) If, after mobing the right pointer n steps forward, it became NULL, it means the head node is the target for removal. In this case, return head.next as the new head of the linked list, effectively removing the original head node.

   4) If the right pointer hasn't reached the end after moving n steps, move both the right and left pointers forward by one step at a time, maintaining the gap between them. This ensures that when the right pointer reaches the end of the linked list, the left pointer will be positioned just before the node that needs to be removed.

   5) Once the right pointer reaches the end of the linked list, update left.next to left.next.next. This action skips over the target node, effectively removing it from the linked list.

   6) Finally, return the original head, which now points to the updated linked list with the nth node removed.

 

# Definition for a Linked List node
# class LinkedListNode:
#     def __init__(self, data, next=None):
#         self.data = data
#         self.next = next

from linked_list import LinkedList
from print_list import print_list_with_forward_arrow

def remove_nth_last_node(head, n):
    # Point two pointers, right and left, at head.
    right = head
    left = head

    # Move right pointer n elements away from the left pointer.
    for i in range(n):
        right = right.next
    
    # Removal of the head node.
    if not right:
        return head.next
    
    # Move both pointers until right pointer reaches the last node.
    while right.next:
        right = right.next
        left = left.next

        # At this point, left pointer points to (n-1)th element.
        # So link it to next to next element of left.
    left.next = left.next.next

    return head

# Definition for a Linked List node
# class LinkedListNode:
#     def __init__(self, data, next=None):
#         self.data = data
#         self.next = next

from linked_list import LinkedList
from linked_list_node import LinkedListNode

def remove_nth_last_node(head, n):
    right = head
    left = head
    
    for i in range(n):
      right = right.next
    
    # right 의 위치를 n+1까지 옮긴경우가 None이 된다면,
    # 제거되어야할 뒤에서 n번째 노드는 head임
    if not right: #  right == None
      return head.next # 첫 번째 노드 삭제 (head 변경) head.next를 반환하면 head가 삭제됨
    
    # linked List 는 인덱스를 사용하지 않고,
    # 각 노드는 .next를 통해 다음 노드를 가리킴
    while right.next: # right.next 가 None이 아닐 때만 반복됨
      right = right.next
      left = left.next
      
    left.next = left.next.next
        
    return head

Solution

1. Two pointers, right and left, are set at the head node.

2. Move the right pointer n steps forward.

3. If right reaches NULL, return head's next node.

4. Otherwise, move both right and left pointers forward till right reaces the last node.

5. Update the left.next to point to left.next.next, effectively removing the target node.

6. Return head.

 

Time complexity: O(n)

Where n is the number of nodes in the linked list.

 

Space complexity: O(1)

We use space to store two pointers.