Linked List Operations (Reversal, Merging, Deletion)

Reverse Linked List (LeetCode 206)

Iterative (Preferred for production to avoid stack overflow):

ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode nextTemp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nextTemp;
    }
    return prev;
}

Recursive:

ListNode reverseListRec(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseListRec(head.next);
    head.next.next = head;  // Make successor point back to current
    head.next = null;
    return newHead;
}

Reverse Linked List II (LeetCode 92): Reverse nodes within range [left, right] using a dummy node:

ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0, head);
    ListNode pre = dummy;
    for (int i = 1; i < left; i++) pre = pre.next;

    ListNode cur = pre.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy.next;
}

Merge Two Sorted Lists (LeetCode 21)

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { 
            cur.next = l1; 
            l1 = l1.next; 
        } else { 
            cur.next = l2; 
            l2 = l2.next; 
        }
        cur = cur.next;
    }
    cur.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Merge K Sorted Lists (LeetCode 23):

1. Priority Queue (Min-Heap): O(N log k)
2. Divide and Conquer: O(N log k)

// Priority Queue Approach
ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode l : lists) {
        if (l != null) pq.offer(l);
    }
    
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        cur.next = pq.poll();
        cur = cur.next;
        if (cur.next != null) pq.offer(cur.next);
    }
    return dummy.next;
}

Remove N-th Node From End of List (LeetCode 19)

Two Pointers: Move the fast pointer N steps ahead, then move both pointers forward. When fast reaches the end, slow will be right before the target node:

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    // Move fast ahead by n+1 steps so slow stops on the node BEFORE the target
    for (int i = 0; i <= n; i++) fast = fast.next; 
    
    while (fast != null) { 
        fast = fast.next; 
        slow = slow.next; 
    }
    slow.next = slow.next.next;
    return dummy.next;
}

Remove Duplicates from Sorted List

Keep One (LeetCode 83):

ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    while (cur != null && cur.next != null) {
        if (cur.val == cur.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return head;
}

Keep None (LeetCode 82): Skip the entire sequence if duplicates are detected:

ListNode deleteDuplicatesAll(ListNode head) {
    ListNode dummy = new ListNode(0, head), pre = dummy;
    while (pre.next != null) {
        ListNode cur = pre.next;
        if (cur.next != null && cur.val == cur.next.val) {
            int duplicateVal = cur.val;
            // Skip all nodes with this value
            while (pre.next != null && pre.next.val == duplicateVal) {
                pre.next = pre.next.next;
            }
        } else {
            pre = pre.next;
        }
    }
    return dummy.next;
}