两两交换链表中的节点

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的头节点。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路

核心思路是通过「虚拟头节点 + 节点删除 / 插入」的方式实现两两交换：

1. 先创建一个**虚拟头节点（dummy）**指向原链表头节点，避免处理头节点交换的特殊情况；
2. 遍历链表时，每次定位到需要交换的两个相邻节点（记为 first、second）；
3. 先将 first 节点从原位置'删除'，再将 first 节点插入到 second 节点的后面；
4. 移动遍历指针，重复上述过程直到所有两两节点交换完成。

执行流程

1. 初始化虚拟头节点 dummy 指向 head。
2. 定义当前指针 cur 指向 dummy。
3. 循环判断 cur.next 和 cur.next.next 是否非空。
4. 记录 first 为 cur.next。
5. 更新 cur.next 为 cur.next.next（跳过 first）。
6. 记录 second 为 cur.next.next。
7. 将 cur.next.next 指向 first。
8. 将 first.next 指向 second。
9. 更新 cur 为 first（即新的 cur.next）。
10. 重复直至链表末尾。

代码实现

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