Remove Nth Node from End

package io.thecodeforge.list;

/**
 * One-pass remove-nth-from-end with trace output for learning and debugging.
 */
public class RemoveNthFromEndDemo {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

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

        // Advance fast n+1 steps to create the gap
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

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

        // Delete: skip the target node
        slow.next = slow.next.next;

        return dummy.next;
    }

    static String listToString(ListNode head) {
        StringBuilder sb = new StringBuilder();
        ListNode current = head;
        while (current != null) {
            sb.append(current.val);
            if (current.next != null) sb.append(" -> ");
            current = current.next;
        }
        return sb.toString();
    }

    static ListNode buildList(int[] values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int val : values) {
            tail.next = new ListNode(val);
            tail = tail.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        // Test 1: Remove middle node
        ListNode list1 = buildList(new int[]{1, 2, 3, 4, 5});
        System.out.println("Before: " + listToString(list1));
        ListNode result1 = removeNthFromEnd(list1, 2);
        System.out.println("After (remove 2nd from end): " + listToString(result1));

        // Test 2: Remove head (n == listLength)
        ListNode list2 = buildList(new int[]{1, 2, 3});
        ListNode result2 = removeNthFromEnd(list2, 3);
        System.out.println("Remove head (3rd from 3): " + listToString(result2));

        // Test 3: Remove tail (n == 1)
        ListNode list3 = buildList(new int[]{1, 2, 3});
        ListNode result3 = removeNthFromEnd(list3, 1);
        System.out.println("Remove tail (1st from end): " 4: Single node list
        ListNode list4 = buildList(new int[]{42});
        ListNode result4 = removeNthFromEnd(list4, 1);
        System.out.println("Single node removed: " + (result4 == null ? "(empty)" : listToString(result4)));

        // Test 5: Two node list, remove first
        ListNode list5 = buildList(new int[]{10, 20});
        ListNode result5 = removeNthFromEnd(list5, 2);
        System.out.println("Two nodes, remove head: " + listToString(result5));
    }
}