(链表专题) 24. 两两交换链表中的节点 ——【Leetcode每日一题】

24. 两两交换链表中的节点

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路：

法一：迭代

链表操作的最重要的是，一个结点的next指向别的结点时，该节点原来后面的那个结点不能丢，要能取到；

要使用迭代，要找多可以迭代的单元，本题的迭代单元为需要交换的两结点。

• 要使迭代过程中，所有结点都不丢失，至少还需要两个指针，这里设为 pre 和 tem ，分别为迭代单元的前一个结点，和迭代单元的第一个结点，
• 迭代步骤如图所示：

• 整理得，进入下一个迭代单元：

法二：递归

• 每一层递归结束后，都返回交换完成后的头结点；
• 每个函数交换两个结点，至少需要两个指针，如图：

代码：(Java、C++)

法一：迭代
Java

/* Definition for singly-linked list.* 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 pre = new ListNode();pre.next = head;ListNode tem = head;head = pre;while(tem != null && tem.next != null){pre.next = tem.next;tem.next = pre.next.next;pre.next.next = tem;pre = pre.next.next;tem = tem.next;}return head.next;}
}

C++

/* 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* pre = new ListNode();pre->next = head;ListNode* tem = head;head = pre;while(tem != NULL && tem->next != NULL){pre->next = tem->next;tem->next = pre->next->next;pre->next->next = tem;pre = pre->next->next;tem = tem->next;}return head->next;}
};

法二：递归

Java

/* Definition for singly-linked list.* 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) {if(head == null || head.next == null){return head;}ListNode newHead = head.next;head.next = swapPairs(newHead.next);newHead.next = head;return newHead;}
}

C++

/* 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) {if(head == NULL || head->next == NULL){return head;}ListNode* newHead = head->next;head->next = swapPairs(newHead->next);newHead->next = head;return newHead;}
};

运行结果：

复杂度分析：

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

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！