题目描述

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

解题思路

交换链表中相邻节点的问题可以通过迭代或递归来解决。本文将介绍两种方法：

方法一：迭代法

1. 使用一个虚拟头节点dummy，指向链表的实际头节点head，这样可以简化头节点的处理。
2. 使用指针prev指向需要交换节点的前一个节点，初始化为dummy。
3. cur指向当前要交换的两个节点中的第一个节点，第二个节点由cur->next指向。
4. 交换cur和cur->next中的两个节点，然后将指针前移，继续交换下一个一对节点直至链表末尾。

方法二：递归法

1. 如果链表为空或者只有一个节点，直接返回头节点。
2. 递归交换后续节点，并将当前节点与后续节点交换。

接下来是两种方法的具体实现。

算法实现

方法一：迭代法实现(C++实现)

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* temp = dummyHead;while (temp->next != nullptr && temp->next->next != nullptr) {ListNode* node1 = temp->next;ListNode* node2 = temp->next->next;temp->next = node2;node1->next = node2->next;node2->next = node1;temp = node1;}ListNode* ans = dummyHead->next;delete dummyHead;return ans;}
};

方法二：递归法实现（C++实现）

class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}ListNode* newHead = head->next;head->next = swapPairs(newHead->next);newHead->next = head;return newHead;}
};

复杂度分析

• 方法一：迭代法

  • 时间复杂度：O(n)，其中n是链表的长度。每两个节点进行一次交换，总体需要遍历整个链表。
  • 空间复杂度：O(1)，只使用了有限的额外空间。

• 方法二：递归法

  • 时间复杂度：O(n)，每两个节点进行一次交换，总体需要遍历整个链表。
  • 空间复杂度：O(n)，因为使用了递归调用，递归调用栈的深度取决于链表的长度。

总结

通过本文，我们介绍了两种解决LeetCode24题目中两两交换链表节点的方法：迭代法和递归法。两种方法都能有效地解决问题，但其不同点在于实现的风格和空间复杂度。迭代方法使用常数空间，适用于不希望使用递归的场景。而递归方法实现较为简洁，但占用较多栈空间。在实际应用中，可以根据具体需求选择合适的方法来解决这个问题。

希望这篇博客能对你有所帮助。如果有任何问题，欢迎随时讨论。