链表节点两两交换：Java 递归与迭代实战

链表节点两两交换：Java 递归与迭代实战

链表操作是面试和工程中的高频考点。两两交换节点看似简单，实则考察对指针指向和边界条件的把控。掌握它，能帮你建立更清晰的递归与迭代思维。

场景类比

生活中类似'交换'的场景很多，比如排队时两人互换位置，或者书架上相邻书籍调换。在链表中，这意味着调整 next 指针的指向，让节点顺序发生翻转。

实际业务中，这类操作常用于数据局部重排、任务队列优先级调整等场景。

三种解法分析

1. 递归法

思路：每次处理当前节点和下一个节点，交换它们的位置，然后递归处理剩余的链表。终止条件是当前节点为空或下一个节点为空。

• 时间复杂度：O(n)
• 空间复杂度：O(n)，受递归调用栈影响

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

2. 迭代法（带哑节点）

思路：引入一个哑节点作为辅助，方便处理头节点交换。每次处理一对节点，调整指针完成交换，然后移动到下一对节点。这是最推荐的工程实践方案。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;

     (head !=  && head.next != ) {
           head;
           head.next;

        
        first.next = second.next;
        second.next = first;
        prev.next = second;

        
        prev = first;
        head = first.next;
    }
     dummy.next;
}