Swapping Nodes in Pairs

Problem: Given a linked list, swap every two adjacent nodes and return its head.

Iterative Approach:

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

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = prev.next.next;
            
            // Swap nodes
            first.next = second.next;
            second.next = first;
            prev.next = second;
            
            // Move to next pair
            prev = first;
        }
        
        return dummy.next;
    }
}

Recursive Approach:

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        
        return newHead;
    }
}

Removing the Nth Node from End of List

Problem: Given a linked list, remove the nth node from the end of the list and return its head.

Two-Pointer Approach:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = head;
        
        // Move second n nodes ahead
        for (int i = 0; i < n; i++) {
            second = second.next;
        }
        
        // Move both until second reaches the end
        while (second != null) {
            first = first.next;
            second = second.next;
        }
        
        // Remove the nth node from end
        first.next = first.next.next;
        
        return dummy.next;
    }
}

Intersection of Two Linked Lists

Problem: Find the node where two linked lists intersect.

Length Difference Approach:

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        // Calculate lengths of both lists
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        // Traverse the longer list by the difference in lengths
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }
        
        // Traverse both lists until intersection is found
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        
        return headA;
    }
    
    private int getLength(ListNode node) {
        int length = 0;
        while (node != null) {
            node = node.next;
            length++;
        }
        return length;
    }
}

Clever Two-Pointer Approach:

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        // When either pointer reaches the end, redirect it to the other list's head
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        
        return pA;
    }
}

Detecting a Cycle in a Linked List

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

Floyd's Cycle Detection Algorithm:

class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        // Find the meeting point
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                // Cycle detected, find the start of the cycle
                ListNode start = head;
                while (start != slow) {
                    start = start.next;
                    slow = slow.next;
                }
                return start;
            }
        }
        
        return null; // No cycle
    }
}