Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Please try to solve the problem by one pass.

/*
Definition for singly-linked list.

public class Node {
  int val;
  Node next;
  Node(int x) { val = x; }
}
*/

public class Solution {
  public Node removeFromEnd(Node head, int n) {
    
  }
}

This problem is selected from LeetCode.

Solution

In this problem we could setup a fast pointer and a slow pointer. From the head of the linked list, the fast pointer starts moving first. After n steps, the slow pointer starts moving. The fast pointer is always n step ahead of the slow pointer. When the fast pointer reaches the end of the linked list, the slow pointer reaches the previous node of the target. Then we could easily remove the target node by setting the next pointer of the previous node to the the next pointer of the target.

public class Solution {
  public ListNode removeFromEnd(ListNode head, int n) {
      
    ListNode fast = head;
    
    // moving the fast pointer 
    while(n-- > 0) 
      fast = fast.next;
    
    // if the fast pointer reaches
    // the end of the linked list,
    // that means the head is the
    // target
    if(fast == null) 
      return head.next;
    
    // moving the slow pointer
    // with the fast pointer
    ListNode slow = head;
    while(fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    slow.next = slow.next.next;
    
    return head;
  }
}

RelatedPost