两两交换链表节点 · 奇偶链表 · 链表加法

两两交换链表中的节点（LeetCode 24）

将相邻两个节点互换位置：

// 迭代（推荐）
ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0, head), pre = dummy;
    while (pre.next != null && pre.next.next != null) {
        ListNode a = pre.next, b = pre.next.next;
        a.next = b.next;
        b.next = a;
        pre.next = b;
        pre = a;  // 移动到下一组的前驱
    }
    return dummy.next;
}

// 递归
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;
}

奇偶链表（LeetCode 328）

将奇数位（1、3、5…）节点排前，偶数位（2、4、6…）排后：

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;
    return head;
}

两数相加（LeetCode 2）

链表逆序存储数字，两数相加：

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;
}

两数相加 II（LeetCode 445）：链表正序存储（高位在前），需要先反转或用栈：

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);
        node.next = head;
        head = node;
    }
    return head;
}

回文链表（LeetCode 234）

O(n) 时间 O(1) 空间：

boolean isPalindrome(ListNode head) {
    // 1. 快慢指针找中点
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. 反转后半部分
    ListNode reversed = reverse(slow);
    // 3. 比较
    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 next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

分隔链表（LeetCode 86）

将所有小于 x 的节点移到大于等于 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;  // 必须截断尾部
    less.next = greaterHead.next;
    return lessHead.next;
}