Learning Journal

3/2/2024

Remove Nth Node From End of List

Tags: algorithms leetcode two_pointers linked_list

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let end = head;
  let i = 0;

  while(end !== null && i < n + 1) {
      end = end.next;
      i++;
  }


  if(end ===  null) {
      if(i === n) 
        return head.next;
      else if(i < n)
        return null;
  }


  
 let p = head;
  while(end !== null) {
      p = p.next;
      end = end.next;
  }

  p.next = p.next.next;

  return head;

};/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let end = head;
  let i = 0;

  while(end !== null && i < n + 1) {
      end = end.next;
      i++;
  }


  if(end ===  null) {
      if(i === n) 
        return head.next;
      else if(i < n)
        return null;
  }


  
 let p = head;
  while(end !== null) {
      p = p.next;
      end = end.next;
  }

  p.next = p.next.next;

  return head;

};

THE PROBLEM

Solving this problem is fairly simple. Here is my reasoning.

Because you have to remove nth node from the end and this is a linked_list (which means you have no way to know where the end is unless you use a pointer to traverse to the end), you need a pointer to go to the end and then count backward n elements to find the one that you need to remove.

This is a call for the two-pointer trick. You let the first pointer go n step, then start the second pointer. This way, those two pointers will always points n element apart. However, if you want to remove an element in a linked list, you need to reassign the next pointer of its previous element to its next element, effectively remove it from the chain (prev.next = prev.next.next). It means that you don't necessarily need the nth element (the one to be removed) but the one before it, or (n + 1)th element from the end. So, you can let the first pointer go n + 1 step before starting the second pointer. And that happens in the while loop of my code.

However, there is one problem. What if the first pointer reaches the end before n + 1 steps?

Well, in that case, there are two possibilities: it either only moves n steps or less than n steps.

In case the first pointer only moves n steps, the one you need to remove is the head, so you just return head.next. In case the first pointer moves less than n steps but still reaches the end, well it can't happen, because n is guaranteed to be always valid, which means n is always less than or equal to the length of the linked-list, there is no way that the first pointer move less than n steps but still reaches the end.

Revised by ChatGPT

To solve this problem, we can use the two-pointer technique. The goal is to remove the nth node from the end of a linked list. Since we can't directly access the nth node from the end, we need to traverse the list to find it.

Here's the approach:

Two-Pointer Technique: We use two pointers, end and p, where end is initially set to the head of the list. We move end forward by n+1 steps. This is because we want p to eventually point to the node just before the one we need to remove, so we can easily modify the next pointer to skip the nth node.
Edge Cases: If end becomes null after moving n+1 steps, it means the list has exactly n+1 nodes, and the node to be removed is the head. In this case, we return head.next. If end is null after moving less than n steps, it contradicts the problem's constraint that n is always valid. Therefore, this case won't occur.
Traverse the List: Once end has moved n+1 steps, we start moving both end and p forward simultaneously until end reaches the end of the list. At this point, p will be pointing to the node just before the one to be removed.
Removed the Node: We skip the nth node by setting p.next = p.next.next.
Return the Head: Finally, we return the head of the modified list.

This approach ensures that we can remove the nth node from the end with just one pass through the list.