链表两两交换的常见写法

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的头节点。这里不能只改节点里的值，得真的把节点位置换掉。

思路

这题最省心的写法，是先补一个虚拟头节点，再按两个节点一组去处理。这样做的好处很直接：头节点也能和普通节点一样处理，不用单独分支。

每一轮都盯着 cur.next 和 cur.next.next。前者是这一组里的第一个节点 first，后者是第二个节点 second。交换的时候不需要真的'搬家'两次，链表指针改四处就够了：先让 cur.next 跳过 first，指向 second；再让 second.next 指向 first；最后把 first.next 接回后面的剩余链表。

我更喜欢把 cur 留在已经处理好的那一段尾部。这样下一轮直接从新位置继续，不容易把指针绕乱。这个写法看起来步骤多，实际比递归稳定，也更适合顺手写一遍过。

执行流程

1. 创建虚拟头节点 dummy，让它指向 head。
2. 定义指针 cur 指向 dummy。
3. 只要 cur.next 和 cur.next.next 都存在，就继续交换。
4. 记录当前这一组的第一个节点 first = cur.next。
5. 让 cur.next 指向 second，也就是 cur.next.next。
6. 再把 second.next 指向 first。
7. first.next 接回剩余链表。
8. cur 后移到 first，准备处理下一组。

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        ListNode head = new ListNode(Integer.parseInt(s[0]));
        ListNode cur = head;
        for (int i = 1; i < s.length; i++) {
            ListNode node = new ListNode(Integer.parseInt(s[i]));
            cur.next = node;
            cur = cur.next;
        }
        ListNode newHead = swapPairs(head);
        cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            cur.next = cur.next.next;
            ListNode second = cur.next.next;
            cur.next.next = first;
            first.next = second;
            cur = cur.next.next;
        }
        return dummy.next;
    }
}

小结

这类题的关键不在算法复杂度，而在指针顺序。只要先想清楚'谁连谁'，再动手改指针，基本不会写崩。虚拟头节点是个小成本，但回报很高的习惯。