Remove Nth Node From End of List Problem and Solution

1. Introduction

A comprehensive guide to solving the "Remove Nth Node From End of List" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "Remove Nth Node From End of List" problem involves removing the nth node from the end of a singly linked list and returning the head of the modified list.

2. Problem

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

3. Solution in C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *start = new ListNode(0), *fast = start, *slow = start;
    start->next = head;
    for (int i = 0; i <= n; ++i) fast = fast->next;
    while (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return start->next;
}

// Example usage
int main() {
    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* res = removeNthFromEnd(head, 2);
    while (res != nullptr) {
        cout << res->val << " ";
        res = res->next;
    }
    return 0;
}

Output:

1 2 3 5

Explanation:

1. removeNthFromEnd in C++ uses two pointers: fast and slow.

2. fast advances n steps ahead of slow.

3. They move together until fast reaches the end, positioning slow just before the node to remove.

4. The node is removed by changing pointers, and the modified list head is returned.

4. Solution in Java

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

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        start.next = head;
        for (int i = 1; i <= n + 1; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return start.next;
    }

    // Example usage
    public static void main(String[] args) {
        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 res = removeNthFromEnd(head, 2);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }
}

Output:

1 2 3 5

Explanation:

1. Java's removeNthFromEnd method follows a similar two-pointer approach as in C++.

2. fast pointer advances n + 1 steps to be ahead of slow.

3. When fast reaches the end, slow is just before the target node.

4. Remove the node and return the modified list head.

5. Solution in Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
result = remove_nth_from_end(head, 2)
while result:
    print(result.val, end=" ")
    result = result.next

Output:

1 2 3 5

Explanation:

1. In Python, a dummy node is used to simplify edge cases.

2. The two-pointer approach is employed with fast moving n + 1 steps ahead of slow.

3. Once fast is None, slow is at the node before the one to be removed.

4. The node is skipped and the new list head is returned.