Remove Nth Node From End of List medium

Problem Statement

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

Example 1

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2

Input: head = [1], n = 1 Output: []

Steps

1. Handle Edge Cases: Check for null head (empty list) or n being less than or equal to 0 or greater than the list's length. Return the head if these conditions are true (or throw an exception, depending on desired behavior).

2. First Pass: Find List Length: Traverse the list once to determine its length.

3. Second Pass (Optimized): Use two pointers, fast and slow. Initially, both point to the head. Move fast n steps forward. Then, move both fast and slow simultaneously until fast reaches the end of the list. At this point, slow will be pointing to the node before the nth node from the end.

4. Remove the Node: To remove the node, update the next pointer of the node before the nth node from the end to skip over the nth node.

5. Return the Head: Return the modified head of the linked list.

Explanation

The key to efficiently solving this problem without multiple passes is using the two-pointer technique. The fast pointer moves ahead by n steps. The gap between fast and slow is maintained at n. When fast reaches the end, slow is perfectly positioned to remove the nth node from the end. This ensures we only traverse the list twice (essentially once, due to the combined passes).

Code

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        // Handle edge cases
        if (head == null || n <= 0) {
            return head; 
        }

        // Find the length of the linked list
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // If n is greater than the length, nothing to remove
        if (n > length) {
            return head;
        }

        //Two pointer approach
        ListNode fast = head;
        ListNode slow = head;

        //Move fast pointer n steps ahead
        for(int i=0; i<n; i++){
            fast = fast.next;
        }

        //if n is equal to length, remove the head node.
        if(fast == null)
        {
            return head.next;
        }

        //Move both pointers until fast reaches the end.
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        //Remove the node
        slow.next = slow.next.next;

        return head;
    }
}

Complexity

• Time Complexity: O(L), where L is the length of the linked list. We traverse the list at most twice.
• Space Complexity: O(1). We use only a constant amount of extra space for pointers.