Swap Nodes in Pairs · Odd Even Linked List · List Addition

Swap Nodes in Pairs (LeetCode 24)

Swap every two adjacent nodes and return its head.

// Iterative Approach (Recommended)
ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0, head), pre = dummy;
    while (pre.next != null && pre.next.next != null) {
        ListNode a = pre.next;
        ListNode b = pre.next.next;
        
        // Swapping
        a.next = b.next;
        b.next = a;
        pre.next = b;
        
        // Move pre to the end of the swapped pair
        pre = a;
    }
    return dummy.next;
}

// Recursive Approach
ListNode swapPairsRec(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode b = head.next;
    head.next = swapPairsRec(b.next);
    b.next = head;
    return b;
}

Odd Even Linked List (LeetCode 328)

Group all odd-indexed nodes (1st, 3rd, 5th...) together followed by the even-indexed nodes.

ListNode oddEvenList(ListNode head) {
    if (head == null) return null;
    ListNode odd = head, even = head.next, evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead; // Connect end of odd list to head of even list
    return head;
}

Add Two Numbers (LeetCode 2)

Numbers are stored in reverse order (least significant digit first).

ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        
        carry = sum / 10;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
    }
    return dummy.next;
}

Add Two Numbers II (LeetCode 445): Numbers are stored in forward order. Use stacks or reverse the lists first.

ListNode addTwoNumbersII(ListNode l1, ListNode l2) {
    Deque<Integer> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
    while (l1 != null) { s1.push(l1.val); l1 = l1.next; }
    while (l2 != null) { s2.push(l2.val); l2 = l2.next; }

    int carry = 0;
    ListNode head = null;
    while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
        int sum = carry;
        if (!s1.isEmpty()) sum += s1.pop();
        if (!s2.isEmpty()) sum += s2.pop();
        
        carry = sum / 10;
        ListNode node = new ListNode(sum % 10);
        // Build the result list backward
        node.next = head;
        head = node;
    }
    return head;
}

Palindrome Linked List (LeetCode 234)

Standard O(n) time and O(1) space implementation:

boolean isPalindrome(ListNode head) {
    // 1. Find midpoint
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 2. Reverse second half
    ListNode reversed = reverse(slow);
    
    // 3. Comparison
    ListNode p1 = head, p2 = reversed;
    while (p2 != null) {
        if (p1.val != p2.val) return false;
        p1 = p1.next; 
        p2 = p2.next;
    }
    return true;
}

private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode nextTemp = head.next;
        head.next = prev;
        prev = head;
        head = nextTemp;
    }
    return prev;
}

Partition List (LeetCode 86)

Partition a list such that all nodes less than x come before nodes greater than or equal to x.

ListNode partition(ListNode head, int x) {
    ListNode lessHead = new ListNode(0), greaterHead = new ListNode(0);
    ListNode less = lessHead, greater = greaterHead;
    
    while (head != null) {
        if (head.val < x) { 
            less.next = head; 
            less = less.next; 
        } else { 
            greater.next = head; 
            greater = greater.next; 
        }
        head = head.next;
    }
    
    greater.next = null;  // Crucial: truncate the tail to avoid cycles
    less.next = greaterHead.next;
    return lessHead.next;
}