Remove Nth Node from End of List – Linked List – Two Pointers Technique

Welcome back, coders! Today, we’re tackling an interesting Linked List problem from LeetCode: Remove the Nth Node from the End of a List. This problem is a great introduction to the two pointers technique, which is not only elegant but also highly efficient for dealing with linked lists. Let’s dive into the problem, break down the solution, and write some code.

Problem Description:

We’re given the head of a singly linked list and an integer n. The goal is to remove the nth node from the end of the list and return the modified list. You can read full description in LeetCode.com

For example:

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

In this example, we remove the 2nd node from the end, which is 4, and return the modified list.

Approach Overview:

1. Understanding the Linked List:

In a linked list, every node points to the next node in the list, and the end is indicated by a null reference. If we want to remove a node, we need to change the next pointer of the previous node to skip over the node we want to remove.

2. Challenges:

The problem requires removing a node when we’re given its position from the end of the list. The trick here is that we cannot directly traverse backward in a singly linked list. So, how do we handle it?

3. Two-Pointer Technique:

To solve this, we can use a clever approach involving two pointers, often called slow and fast. Here’s the idea:

• We move the fast pointer n+1 steps ahead.
• Then, we move both fast and slow pointers one step at a time until fast reaches the end of the list.
• When fast reaches the end, the slow pointer will be just before the node we need to remove.

4. Using a Dummy Node:

To handle edge cases, such as removing the head node itself, we introduce a dummy node at the beginning of the list. This dummy node points to the head of the list and simplifies the logic for edge cases like removing the first node.

Solution Code:

Here’s the Java solution using the two-pointer technique:

/**
 * 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) {
        // Create a dummy node to handle edge cases (like removing the head node)
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // Initialize two pointers, both starting at the dummy node
        ListNode fast = dummy;
        ListNode slow = dummy;

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

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

        // Skip the nth node from the end by updating the next pointer
        slow.next = slow.next.next;

        // Return the modified list, which starts from dummy.next
        return dummy.next;
    }
}

Step-by-Step Breakdown:

1. Dummy Node Creation: We create a dummy node, which allows us to avoid special cases when removing the head. The dummy node’s next pointer is initialized to the head of the list.
2. Initialize Two Pointers: We initialize two pointers, slow and fast, both starting from the dummy node.
3. Move the Fast Pointer Ahead: The fast pointer is moved ahead by n + 1 positions. This ensures that when fast reaches the end, slow will be just before the node we want to remove.
4. Simultaneous Movement: Once the fast pointer is ahead by n + 1 steps, we move both slow and fast pointers one step at a time. By the time the fast pointer reaches the end, the slow pointer will be just before the node we need to remove.
5. Skip the Target Node: To remove the nth node, we simply update slow.next to point to slow.next.next, effectively skipping over the target node.
6. Return the Updated List: Finally, we return dummy.next, which is the head of the modified list.

Time and Space Complexity:

• Time Complexity: O(L), where L is the number of nodes in the list. We only traverse the list once with the two pointers.
• Space Complexity: O(1). We are only using a constant amount of extra space.

Key Takeaways:

• The two-pointer technique is a powerful tool for solving problems in linked lists where backward traversal isn’t an option.
• Introducing a dummy node simplifies edge case handling, especially when the node to be removed is the head of the list.
• The solution runs in linear time, making it optimal for larger lists.

---

Conclusion:

This problem is a fantastic example of how a clever approach like the two-pointer technique can simplify a seemingly complex problem. By efficiently managing the traversal of the list, we can remove the nth node from the end in one pass, ensuring an optimal and elegant solution.

If you found this tutorial helpful, don’t forget to subscribe to our YouTube channel for more coding tutorials, and check out more content here on SoundOfCode.com. Happy coding!