【LeetCode 热题 100】24. 两两交换链表中的节点——（解法一）迭代+哨兵

Problem: 24. 两两交换链表中的节点
题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

整体思路

这段代码旨在解决一个经典的链表操作问题：两两交换链表中的节点 (Swap Nodes in Pairs)。问题要求将链表中每两个相邻的节点进行交换，并返回交换后的链表。例如，1->2->3->4 应变为 2->1->4->3。

该算法采用了一种 迭代 的方法，通过精心设计的指针操作来完成节点的交换。为了简化边界情况（特别是头节点的交换），它也巧妙地运用了 哨兵节点 (Sentinel Node)。

其核心逻辑步骤如下：

1. 初始化：

   • 哨兵节点：创建一个 dummy 节点，其 next 指向原始链表的头节点 head。这使得对第一对节点的交换与其他节点的交换逻辑完全统一。
   • 指针设置：
     • left 指针：初始化为 dummy。这个指针将始终指向待交换的一对节点的前一个节点。它的作用是连接上一组交换好的部分和当前正在交换的部分。
     • right 指针：初始化为 head。这个指针将始终指向待交换的一对节点中的第一个节点。

2. 迭代交换：

   • 算法使用一个 while 循环来遍历并交换节点对。
   • 循环条件：while (null != right && null != right.next)。这个条件确保了至少还有一对完整的节点（right 和 right.next）可供交换。如果链表为空、只有一个节点，或者只剩最后一个节点，循环都不会执行。
   • 在循环内部（核心交换逻辑）：
     • 假设当前结构是 ... -> left -> right -> right.next -> ...。目标是变为 ... -> left -> right.next -> right -> ...。
     • left.next = right.next;：首先，将 left 的 next 指针指向 right 的下一个节点。这是将交换后的新“头”节点连接到前面的链表上。
     • right.next = right.next.next;：接着，将 right 的 next 指针指向它原来下一个节点的下一个节点，即跳过中间的节点。
     • left.next.next = right;：最后，将原来 right.next 的 next 指针指向 right，完成两个节点的交换。
   • 指针前移：
     • left = right;：完成一对交换后，right 节点现在是这一对中的第二个（在后面）。我们需要为下一轮交换做准备，所以将 left 指针移动到 right 的位置。
     • right = left.next;：将 right 指针移动到下一对节点的第一个节点。

3. 返回结果：

   • 循环结束后，所有节点对都已交换完毕。dummy.next 指向了交换后链表的真正头节点，将其返回。

完整代码

/**
 * Definition for singly-linked list.
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    /**
     * 两两交换链表中的节点。
     * @param head 原始链表的头节点
     * @return 交换后链表的头节点
     */
    public ListNode swapPairs(ListNode head) {
        // 创建一个哨兵节点，简化头节点交换的逻辑。
        ListNode dummy = new ListNode(0, head);
        
        // left 指针指向待交换对的前一个节点。
        ListNode left = dummy;
        // right 指针指向待交换对的第一个节点。
        ListNode right = head;
        
        // 循环条件：确保至少还有一对完整的节点可以交换。
        while (null != right && null != right.next) {
            // 核心交换逻辑，可以想象为三步指针重定向：
            // 假设原始是: left -> n1 -> n2 -> ...
            // 其中 n1 是 right, n2 是 right.next
            
            // 1. left 的 next 指向 n2
            left.next = right.next;
            
            // 2. n1 的 next 指向 n2 原来的 next
            right.next = right.next.next;
            
            // 3. n2 的 next 指向 n1
            left.next.next = right;
            
            // 交换后，链表变为: left -> n2 -> n1 -> ...
            
            // 为下一轮交换做准备，移动指针：
            // left 移动到 n1 的位置
            left = right;
            // right 移动到 n1 的下一个位置，即下一对的第一个节点
            right = left.next;
        }
        
        // 返回哨兵节点的下一个节点，即新链表的头。
        return dummy.next;
    }
}

时空复杂度

时间复杂度：O(N)

1. 循环次数：while 循环遍历整个链表。right 指针每次前进两步（逻辑上）。整个链表被扫描了一次。
2. 每次操作：在循环的每一次迭代中，执行的都是常数次（固定次数）的指针赋值操作。

综合分析：
算法的时间复杂度与链表的长度 N 成线性关系。因此，时间复杂度为 O(N)。

空间复杂度：O(1)

1. 主要存储开销：算法只创建了 dummy, left, right 等几个额外的指针变量。
2. 空间大小：这些变量的数量是固定的，与输入链表的长度 N 无关。

综合分析：
算法没有使用任何与输入规模成比例的额外数据结构。因此，其额外辅助空间复杂度为 O(1)。这是一个高效的原地算法。