Remove N-th node from back of LinkedList

Problem Overview

The problem "Remove Nth Node From End of List" is a common problem that evaluates one's understanding and manipulation of linked lists. The challenge requires you to remove the n-th node from the end of a singly linked list and return its head.

Understanding the Problem

In a singly linked list, each node points to the next node, and removing a node involves changing the pointers such that the node before the node to be removed points to the node after it. In this problem, you are required to remove the n-th node from the end rather than from the beginning. This might seem tricky at first because you need to traverse the list to calculate the total number of nodes.

Let's understand with an example:

• Consider the list: 1 -> 2 -> 3 -> 4 -> 5
• If n = 2, the desired output is: 1 -> 2 -> 3 -> 5 (removing the 4th node from the end).

Key DSA Concepts and Theory

Linked List

A linked list is a linear data structure where each element is a separate object. Each node of a list is made up of two items - the data and a reference (or link) to the next node. The last node has a reference to null.

Advantages:

• Dynamic size.
• Ease of insertion/deletion.

Disadvantages:

• Random access is not allowed.
• Extra memory space for a pointer is required with each element.

Two-Pointer Technique

This problem employs a neat trick using two pointers for efficient computation:

• Slow and Fast Pointer: We can develop a single-pass solution using two pointers: one (fast) to reach the end of the list and another (slow) to locate the node before the target node. The idea is to maintain a gap of n nodes between the two pointers.

Solution Approach

To solve this problem, we will use a two-pointer technique to perform the task in a single traversal. The idea is to keep a gap of n nodes between the pointers such that when the fast pointer reaches the end, the slow pointer is right before the node to be deleted.

C++ Implementation

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;

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

        // Move both pointers at the same pace
        while (fast != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }

        // Now slow is just before the node to be removed
        slow->next = slow->next->next;

        // Return updated list starting with real head
        return dummy->next;
    }
};

Java Implementation

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;

        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }

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

        slow.next = slow.next.next;

        return dummy.next;
    }
}

Step-by-Step Explanation

1. Initialize: Create a dummy node pointing at the head of the list. Set two pointers, slow and fast, both initially at the dummy node.

2. Advance Fast Pointer: Move the fast pointer n + 1 steps forward to create a gap.

3. Traverse with Both Pointers: Move slow and fast together at the same speed.

4. Deletion: When fast reaches the end, slow will be right before the target node. Adjust the next pointer of slow to exclude the target node.

5. Return Result: Return dummy.next which is the head of the adjusted list.

Time and Space Complexity Analysis

• Time Complexity: O(L), where L is the number of nodes in the linked list. We make a single pass through the list.
• Space Complexity: O(1), as we are using only constant extra space.

Common Mistakes to Avoid

1. Not Handling Single Node Edge Cases: Ensure the solution can handle cases where the list has only one node or when n is equal to the length of the list.
2. Off-by-One Errors: Carefully manage the pointers to ensure you maintain exactly an n node gap between fast and slow.

Similar Problems on LeetCode

• Reverse Linked List - (Question 206)
• Middle of the Linked List - (Question 876)
• Merge Two Sorted Lists - (Question 21)

Additional Resources and References

• Linked List Data Structure - GeeksforGeeks
• Two Pointer Technique - GeeksforGeeks

This article provides a structured explanation for removing the n-th node from the end of a linked list while discussing the underlying theoretical concepts and practical solution approaches with efficient coding examples.