Java 中链表元素的成对交换

成对交换链表节点是指在不改变节点值的情况下，交换列表中相邻的节点。目标是重新排列列表，使每两个连续的节点交换位置，同时保持列表的整体顺序。

此操作可以通过递归或迭代来完成，需要仔细处理指针以避免破坏列表结构。

示例 1：偶数个节点

输入: 10 → 20 → 30 → 40 → 50 → 60

输出: 20 → 10 → 40 → 30 → 60 → 50

解释

• (10,20) 交换 → 20 → 10
• (30,40) 交换 → 40 → 30
• (50,60) 交换 → 60 → 50

示例 2：奇数个节点

输入: 5 → 15 → 25 → 35 → 45

输出: 15 → 5 → 35 → 25 → 45

解释

• (5,15) 交换 → 15 → 5
• (25,35) 交换 → 35 → 25
• 45 由于没有相邻节点可以交换，所以保持不变。

方法：使用递归

递归方法首先将第二个节点设为新的头部，然后对剩余的列表递归调用函数来交换相邻节点。交换完成后，新头节点的 next 指针会指向第一个节点，确保正确链接。

算法

步骤 1: 如果链表为空或只有一个节点，则返回头节点，因为不需要交换。

步骤 2: 将第二个节点存储为 newHead，然后递归调用 函数，从第三个节点开始交换剩余节点。

步骤 3: 将第一个节点的 next 指针设置为递归调用返回的头节点，从而将其链接到更新后的子列表。

步骤 4: 将 newHead（第二个节点）的 next 指针设置为第一个节点，完成前两个节点的交换。

步骤 5: 由于第二个节点现在是修改后列表的第一个节点，因此返回 newHead 作为更新后链表的新的头节点。

实施

文件名: PairwiseSwap.java

输出

 
Original List:
1 2 3 4 5 
List after pairwise swap:
2 1 4 3 5    

时间复杂度: O(N) → 我们遍历列表一次，在每一步执行常数时间的操作。

辅助空间复杂度: O(N) → 由于递归，调用栈使用的空间与列表中节点的数量成正比。

解释

这个 Java 程序使用递归方法交换单链表的相邻节点。ListNode 类定义了节点的结构，而 swapPairs 方法执行交换。如果列表为空或只有一个节点，则按原样返回。否则，它将第二个节点设为新的头部，并递归地交换剩余的列表。

原始的第一个节点被链接到交换后的部分，完成交换。displayList() 方法在交换前后打印列表，main 方法初始化列表并调用 swap 函数来演示其功能。

方法：使用迭代法

迭代方法通过维护一个虚拟节点并迭代更新指针来交换相邻节点。它在循环中处理节点对，调整链接以确保正确重新排序，而无需使用递归。

算法

步骤 1: 如果列表为空或只有一个节点，则不需要交换，因此只需返回列表的头节点，不做任何更改。

步骤 2: 初始化一个虚拟节点以简化逻辑，并将 prev 指向虚拟节点，以跟踪在交换节点对之前该节点。

步骤 3: 当至少有两个节点可以交换时，迭代遍历列表，并对每对相邻节点执行交换操作。

步骤 4: 交换节点后，更新指针，使 prev.next 指向第二个节点，first.next 指向第二个节点后面的节点，second.next 指向第一个节点。

步骤 5: 所有节点对都交换完成后，返回 dummy.next 作为修改后列表的新头部，因为虚拟节点用于处理列表开头的交换。

实施

文件名: PairwiseSwap.java

输出

 
Original List:
1 2 3 4 5 
List after pairwise swap:
2 1 4 3 5    

解释

这个 Java 程序实现了一种迭代方法来交换单链表的相邻节点。它首先定义了一个 ListNode 类来表示每个节点，以及一个 swapPairs 方法来执行交换。引入了一个虚拟节点来处理边缘情况，而 prev 指针则跟踪要交换的每个节点对之前的节点。

该方法遍历列表，系统地更新指针以交换相邻节点。此外，displayList 方法在交换前后打印列表。这种方法有效地处理了偶数和奇数长度的列表，确保未配对的节点保持不变。

方法：通过更改链接

该方法通过修改链接而非值来交换相邻节点，使用了三个指针（prev、curr、newHead）。它遍历列表，为每对节点更新链接，并在交换后返回新的头部。

算法

步骤 1: 如果列表为空或只有一个节点，则返回头节点，因为不需要交换。

步骤 2: 将 prev 设置为 null，curr 设置为 head，newHead 设置为 head.next，用于跟踪交换后的新头部。

步骤 3: 当存在两个节点时，更新第二个节点的 next 指向第一个节点，第一个节点的 next 指向下一个未交换的节点。

步骤 4: 如果存在前一个节点，则将其 next 指向交换对的第二个节点，以保持正确的顺序。

步骤 5: 将 prev 移至 curr，将 curr 移至下一个未交换的节点，直到列表末尾。

实施

文件名: PairwiseSwapLinks.java

输出

 
Original List:
1 2 3 4 5 
List after pairwise swap:
2 1 4 3 5    

时间复杂度: O(N) （每个节点被访问一次，并在常数时间内交换）

辅助空间复杂度: O(1) （除了指针外，不使用额外的空间）

解释

这个 Java 程序通过修改链接而不是值来交换单链表的相邻节点。 ListNode 类定义了节点的结构，而 swapPairs 方法则迭代地成对交换节点。

它维护三个指针：prev（前一个节点）、curr（当前节点）和 newHead（将成为交换后列表的新头部）。在每次迭代中，重新排列相邻节点之间的链接以实现交换，同时保持其余节点的顺序。

displayList() 方法在交换前后打印列表，main 方法初始化链表并调用 swap 函数来演示转换。