Remove Nth Node From End of List - Java Solution

1. Introduction

In this post, we explore a common problem in linked list manipulation, namely "Remove Nth Node From End of List". This problem tests one's ability to traverse and modify a linked list, a fundamental data structure in computer science. The challenge involves removing a specific node from the end of a singly linked list.

Problem

Given the head of a linked list, the task is to remove the nth node from the end of the list and then return the head of the modified list.

2. Solution Steps

1. Initialize two pointers: start and end. Both start at the head of the list.

2. Move end forward by n steps so that the gap between start and end is n nodes.

3. Traverse the list with both pointers until end reaches the last node.

4. Remove the nth node from the end by changing the next pointer of the start node.

5. Special case handling for when the removed node is the head of the list.

6. Return the modified head of the list.

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class RemoveNthNodeFromEnd {
    public static void main(String[] args) {
        // Example use case
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode result = removeNthFromEnd(head, 2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }

    // Function to remove the nth node from the end of the list
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode start = dummy, end = dummy;

        // Move end forward so that the gap is n nodes
        for (int i = 1; i <= n + 1; i++) {
            end = end.next;
        }

        // Move start to the node before the one to be deleted
        while (end != null) {
            start = start.next;
            end = end.next;
        }

        // Remove the nth node
        start.next = start.next.next;
        return dummy.next;
    }
}

Output:

1 2 3 5

Explanation:

1. removeNthFromEnd: This function removes the nth node from the end of a linked list.

2. A dummy node is used to simplify edge cases, especially when the head of the list is removed.

3. Two pointers, start and end, are used to find the nth node from the end. end is advanced n steps ahead of start.

4. Both pointers are then moved together until end reaches the end of the list. At this point, start is just before the node to be removed.

5. The next pointer of start is updated to skip the nth node, effectively removing it from the list.

6. The function returns the head of the modified list, which is dummy.next, to handle cases where the original head is removed.

7. This approach efficiently locates and removes the nth node from the end with a single pass through the list.