迭代
解题思路
创建哑结点 dummyHead 令
dummyHead.next = head，temp 表示当前到达的节点，初始时temp = dummyHead，每次需要交换 temp 后面的两个节点；如果 temp 的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换；
否则，获得 temp 后面的两个节点 node1 和 node2 通过更新节点的指针关系实现两两交换节点；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的节点数量，需要对每个节点进行更新指针的操作； -
空间复杂度：
O(1)
代码实现
var swapPairs = function (head) {
const dmy = new ListNode(0, head);
// 定义 tmp 当前指针
let tmp = dmy;
while (tmp.next !== null && tmp.next.next !== null) {
// 定义 node1 和 node2 指针
let node1 = tmp.next;
let node2 = tmp.next.next;
// 反转 node1 node2 指向
tmp.next = node2;
node1.next = node2.next;
node2.next = node1;
// 移动 tmp 指针
tmp = tmp.next.next
}
return dmy.next;
};
头递归
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的节点数量，需要对每个节点进行更新指针的操作； -
空间复杂度：
O(n)，其中 n 是链表的节点数量，空间复杂度主要取决于递归调用的栈空间；
实现代码
var swapPairs = function (head) {
if (head === null || head.next === null) return head;
let node1 = head.next;
let node2 = head.next.next;
node1.next = head; // 反转
head.next = swapPairs(node2);
return node1; // 返回交换完成的子链表
};
尾递归
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的节点数量，需要对每个节点进行更新指针的操作； -
空间复杂度：
O(n)，其中 n 是链表的节点数量，空间复杂度主要取决于递归调用的栈空间；
代码实现
var swapPairs = function (head) {
if (head === null || head.next === null) return head;
let nextNode = head.next;
head.next = swapPairs(head.next.next); // 当前节点指向下下个节点
nextNode.next = head; // 下下个节点指向下个节点
return nextNode; // 返回交换完成的子链表
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 203. 移除链表元素
上一篇
评论
