Remove Nth Node From End of List

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

Follow up: Could you do this in one pass?

Approach1: Two Pass

In this approach, we do a first pass over the Linked List to obtain it's length. With this newfound length we are able to have our pointer situated before the Nth node from the end of the list by substracting the Nth Node from the total length length = length - n. From there, we would simply move a pointer to that postion and remove the Nth Node from End of List.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode current = dummy;
        int length = 0;
        while(current != null){
            length++;
            current = current.next;
        }
        length -= n;
        
        current = dummy;
        while(--length > 0){
            current = current.next;
        }
        current.next = current.next.next;
        return dummy.next;
    }
}

Time: O(n) Space: O(1)

Approach2: One Pass (optimal)

We will effectuate a one-pass solution using two pointers.

• Move one pointer fast --> n steps forward in order to maintain a distance of n between the two pointers

• Once fast pointer is n steps forward, concurrently move both pointers forward until fast reaches the end of the list since it was already in advance.

• When fast pointer reaches end of list, n will be at the position right before the nth node which is ideal since we want ot remove the nth Nod

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        fast = slow = dummy
        
        for _ in range(n):
            fast = fast.next
            
        while fast.next:
            fast = fast.next
            slow = slow.next
            
        slow.next = slow.next.next
        return dummy.next

Time: O(n) Space: O(1)

Java Version (optimal)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode current = dummy;
        int length = 0;
        while(current != null){
            length++;
            current = current.next;
        }
        length -= n;
        
        current = dummy;
        while(--length > 0){
            current = current.next;
        }
        current.next = current.next.next;
        return dummy.next;
    }
}