两两交换链表中的节点
题目要求
本题的目标是实现一个算法，用于交换给定链表中相邻节点的位置。具体来说，就是将链表中的第 1 个节点与第 2 个节点交换，第 3 个节点与第 4 个节点交换，以此类推。如果链表的长度是奇数，那么最后一个节点不需要与前一个节点交换。重要的约束是不能改变节点内部的值，只能通过改变节点之间的链接（即指针）来实现节点的交换。算法完成后，需要返回交换后链表的头节点。
解题思路
解决这个问题的关键在于重新链接链表中的节点，以实现节点的两两交换。以下是解题的步骤：
-
创建一个哨兵节点（dummy node），它的 next 指针指向链表的头节点。这个哨兵节点可以帮助简化链表头部的交换操作，并且最后可以通过哨兵节点来返回新的头节点。
-
初始化两个指针，prev 指针指向哨兵节点，current 指针指向链表的头节点。
-
遍历链表，检查 current 及其 next 节点是否存在。如果只剩下一个或没有节点，则不需要交换，直接结束。
-
如果需要交换，执行以下步骤：
- 将 prev 的 next 指针指向 current 的 next 节点，即将第二个节点移到第一个位置。
- 将 current 的 next 指针指向 current 的 next 的 next 节点，即将第一个节点链接到第三个节点的位置。
- 将 current 的 next 的 next 指针指向 current，即将第二个节点链接到第一个节点的位置。
- 更新 prev 指针为当前的 current 节点。
-
将 current 指针更新为 prev 的 next，即移动到下一对需要交换的节点的第一个位置。
-
重复步骤 3 到 5，直到链表末尾。
-
返回哨兵节点的 next，即交换后的链表头节点。
通过这种方式，我们可以在一次遍历中完成所有的交换操作，而不需要修改任何节点的值。这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。
Golang 版本
type ListNode struct {
Val int
Next *ListNode
}
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
prev := dummy
for head != nil && head.Next != nil {
// Nodes to be swapped
firstNode := head
secondNode := head.Next
// Swapping
prev.Next = secondNode
firstNode.Next = secondNode.Next
secondNode.Next = firstNode
// Reinitializing the head and prev node for next swap
prev = firstNode
head = firstNode.Next // jump to the next pair
}
// Return the new head node.
return dummy.Next
}
这段代码定义了一个链表节点的结构体ListNode，并实现了一个swapPairs函数，该函数接收一个链表的头节点head作为参数，返回两两交换后的链表的头节点。代码中使用了一个哨兵节点dummy来简化边界条件的处理，通过迭代的方式遍历链表，并在每一步中交换相邻的节点。
C++版本
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
while (head && head->next) {
ListNode* firstNode = head;
ListNode* secondNode = head->next;
// Swapping
prev->next = secondNode;
firstNode->next = secondNode->next;
secondNode->next = firstNode;
// Reinitializing the pointers for next swap
prev = firstNode;
head = firstNode->next; // move to the next pair
}
return dummy.next;
}
};
这段 C++代码定义了一个链表节点的结构体ListNode和一个解决方案类Solution。Solution类中的swapPairs成员函数接收一个链表的头节点head作为参数，并返回两两交换后的链表的头节点。代码中使用了一个哨兵节点dummy来简化链表头部的处理，通过迭代的方式遍历链表，并在每一步中交换相邻的节点。
Python 版本
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prev, current = dummy, head
while current and current.next:
# Nodes to be swapped
first_node = current
second_node = current.next
# Swapping
prev.next = second_node
first_node.next = second_node.next
second_node.next = first_node
# Reinitializing the pointers for next swap
prev = first_node
current = first_node.next
return dummy.next
这段 Python 代码定义了一个链表节点的类ListNode和一个解决方案类Solution。Solution类中的swapPairs方法接收一个链表的头节点head作为参数，并返回两两交换后的链表的头节点。代码中使用了一个哨兵节点dummy来简化链表头部的处理，通过迭代的方式遍历链表，并在每一步中交换相邻的节点。
Java 版本
public 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 {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode current = head;
while (current != null && current.next != null) {
// Nodes to be swapped
ListNode firstNode = current;
ListNode secondNode = current.next;
// Swapping
prev.next = secondNode;
firstNode.next = secondNode.next;
secondNode.next = firstNode;
// Reinitializing the pointers for next swap
prev = firstNode;
current = firstNode.next;
}
return dummy.next;
}
}
这段 Java 代码定义了一个链表节点的类ListNode和一个解决方案类Solution。Solution类中的swapPairs方法接收一个链表的头节点head作为参数，并返回两两交换后的链表的头节点。代码中使用了一个哨兵节点dummy来简化链表头部的处理，通过迭代的方式遍历链表，并在每一步中交换相邻的节点。
Rust 版本
#![allow(unused)] fn main() { // Definition for singly-linked list. #[derive(PartialEq, Eq, Clone, Debug)] pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>>, } impl ListNode { #[inline] fn new(val: i32) -> Self { ListNode { next: None, val } } } impl Solution { pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut dummy = Some(Box::new(ListNode { val: 0, next: head })); let mut prev = &mut dummy; while prev.as_ref().unwrap().next.is_some() && prev.as_ref().unwrap().next.as_ref().unwrap().next.is_some() { let mut first = prev.as_mut().unwrap().next.take().unwrap(); let mut second = first.next.take().unwrap(); first.next = second.next.take(); second.next = Some(first); prev.as_mut().unwrap().next = Some(second); prev = &mut prev.as_mut().unwrap().next.as_mut().unwrap().next; } dummy.unwrap().next } } }
这段 Rust 代码定义了一个单链表节点的结构体ListNode和一个解决方案模块Solution。Solution模块中的swap_pairs函数接收一个链表的头节点head作为参数，并返回两两交换后的链表的头节点。代码中使用了一个哨兵节点dummy来简化链表头部的处理，通过迭代的方式遍历链表，并在每一步中交换相邻的节点。在 Rust 中，链表的节点通常通过Option<Box<ListNode>>来表示，以便于处理所有权和可变性。
总结
上面给出了使用不同编程语言实现的解决方案，用于交换给定链表中相邻节点的位置。这些解决方案都采用了迭代的方式遍历链表，并在每一步中交换相邻的节点。它们都使用了一个哨兵节点来简化链表头部的处理，并在不修改节点内部的值的情况下完成了节点的交换。这些解决方案在不同的编程语言中展示了如何通过指针或引用来操作链表节点，实现了相同的算法逻辑。