LeetCode30 - 两两交换链表中的节点

📝 题目描述

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

示例：

示例 1：

1 2	输入：head = [1,2,3,4] 输出：[2,1,4,3]

示例 2：

1 2	输入：head = [] 输出：[]

示例 3：

1 2	输入：head = [1] 输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

💡 解题思路

方法一：递归

可以通过递归的方式实现两两交换链表中的节点。

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。

方法二：迭代

首先还是要创建一个哨兵节点，让头节点也具有一般性。

然后我们一次处理两个节点，这样就符合两两交换的条件，不足两个说明处理结束。

如下图所示：

先让pre指向temp；
然后让ptr指向temp -> next；
最后让temp指向ptr；

做完这些更新 pre 和 ptr 指针，准备下一次迭代。

🔧 代码实现

1、递归

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

2、迭代

/**
 * Definition for singly-linked list.
 * 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 = new ListNode(-1, head);
        ListNode* pre = dummy;
        ListNode* ptr = head;
        while(ptr != nullptr && ptr -> next != nullptr) {
            ListNode* temp = ptr -> next;
            pre -> next = temp;
            ptr -> next = temp -> next;
            temp -> next = ptr;
            // 准备下一波
            pre = ptr;
            ptr = ptr -> next;
        }
        
        ListNode* ans = dummy -> next;
        delete dummy;
        return ans;
    }
};

📊 复杂度分析

1、递归

时间复杂度： $O(n)$ ，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
空间复杂度： $O(n)$ ，其中 n 是链表的节点数量。空间复杂度主要取决于递归调用的栈空间。

2、迭代

时间复杂度： $O(n)$ ，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
空间复杂度： $O(1)$ 。

🎯 总结

核心思想：学会递归的思路。