Remove Linked List Elements (LeetCode 203)

Given the head of a linked list and an integer val, remove all nodes where Node.val == val and return the new head node.

Using a dummy head simplifies handling edge cases, especially when the head node itself needs to be removed. A traversal pointer prev is used to point to the node preceding the one currently being checked.

Note: Without an else block, consecutive nodes matching the target value might be missed.

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return dummy.next;
    }
}

Reverse Linked List (LeetCode 206)

Reverse a singly linked list and return the new head.

The iterative approach uses three pointers: prev, curr, and temp. prev tracks the previous node, curr is the current node being processed, and temp temporarily stores the next node to avoid losing the reference.

Key Points:

1. The loop condition is curr != null because the last node must also be processed to point to the previous node.
2. Initialize prev to null because the new tail (original head) should point to null.
3. Define temp inside the loop to handle empty list cases safely.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

Swap Nodes in Pairs (LeetCode 24)

Swap every two adjacent nodes in a linked list and return its head. Node values must not be modified.

A dummy head is used for uniformity. The pointer anchor points to the node before the pair to be swapped. The loop continues as long as there are at least two nodes left to swap.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode anchor = dummy;
        
        while (anchor.next != null && anchor.next.next != null) {
            ListNode first = anchor.next;
            ListNode second = anchor.next.next;
            ListNode remaining = second.next;
            
            anchor.next = second;
            second.next = first;
            first.next = remaining;
            
            anchor = first;
        }
        return dummy.next;
    }
}

Remove Nth Node From End of List (LeetCode 19)

Remove the n-th node from the end of a linked list and return its head.

Use two pointers, leader and follower, with a dummy head. Advance leader by n + 1 steps first so that when leader reaches the end, follower is positioned right before the target node to be removed.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode leader = dummy;
        ListNode follower = dummy;
        
        for (int i = 0; i <= n; i++) {
            leader = leader.next;
        }
        
        while (leader != null) {
            leader = leader.next;
            follower = follower.next;
        }
        
        follower.next = follower.next.next;
        return dummy.next;
    }
}

Linked List Cycle II (LeetCode 142)

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Use the fast and slow pointer technique. When they meet, reset one pointer to the head and move both at the same speed. The node where they meet again is the cycle's entrance.

Reasoning:

• The fast pointer moves twice as fast as the slow one (f = 2s).
• Let x be the distance from head to cycle entrance, y the distance from entrance to meeting point, and z the remaining cycle length. When they meet: f = x + y + n(y + z), s = x + y. Solving gives x = z + (n-1)(y + z), meaning the distance from head to entrance equals the distance from meeting point to entrance (plus full cycles).

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            
            if (fast == slow) {
                ListNode start = head;
                while (start != slow) {
                    start = start.next;
                    slow = slow.next;
                }
                return start;
            }
        }
        return null;
    }
}