Interview Question Remove Nth Node From End of List

By Fatih KABAKCI

The problem is to be able to delete nth node from end of the list in a given linked list by one passing at a time. Given n will always be valid. So, there is no need to check that out.

Problem #19 - Remove Nth Node From End of List

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

Difficulty: Easy

Solution in Java

package com.fatihkabakci.Easy.RemoveNthNodeFromEndofList;

/**
 * @author fkabakci
 * 
 * Problem Description: 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.
 * 
 * Note: Given n will always be valid. Try to do this in one pass.
 * 
 * Solution:
 * Purpose is to fall down the pointer - slow in front of the node which needs to be deleted.
 * So then, the final part slow.next = slow.next.next; is going to be able to work properly.
 * 
 * 1. Move the pointer - fast to n + 1 forward.
 * 	  if fast is already null during this process
 *       Means that first data demands to be deleted because n is always valid.
 * 2. Move both the pointers fast and slow to forward until fast is null.
 * 3. Connect the apart parts to each other by dropping the node which is wanted to delete.
 * 
 *  */
public class RemoveNthNodeFromEndofList {	
	public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode fast = head, slow = head;
		for (int i = 1; i <= n + 1; i++) {
			// for the first element to be able to deleted.
			if (fast == null)
				return head.next;
			fast = fast.next;
		}

		while (fast != null) {
			fast = fast.next;
			slow = slow.next;
		}

		slow.next = slow.next.next;
		return head;
    }
	
	public static void main(String[] args) {
		RemoveNthNodeFromEndofList r = new RemoveNthNodeFromEndofList();
		ListNode head = Data.init(new int[]{1, 2, 3});
		ListNode remain = r.removeNthFromEnd(head, 1);
		while(remain != null) {
			System.out.print(remain.val + " ->");
			remain = remain.next;
		}
	}
}