网络异常，图片无法展示
|
「这是我参与11月更文挑战的第14天，活动详情查看：2021最后一次更文挑战」
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
网络异常，图片无法展示
|
输入： head = [1,2,3,4] 输出： [2,1,4,3] 复制代码
示例 2：
输入： head = [] 输出： [] 复制代码
示例 3：
输入： head = [1] 输出： [1] 复制代码
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
进阶： 你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
本题其实是 leetcode-25. K 个一组翻转链表 的简化版
对 leetcode-25. K 个一组翻转链表 题解感兴趣的小伙伴可以看我之前这边文章
本题我们只需要找到两个链表节点，然后将它们位置交换，然后将交换后的头节点连接到结果链表的末尾即可
这里我采用两种方式解决问题
题解1
通过递归的方式完成原链表的两两交换
- 首先我们需要一个
swap函数来完成我们递归的逻辑 - 该函数会首先判断剩余待处理链表是否有两个节点，如果没有，则直接返回
head即可 - 首先记录传入链表的第三个节点（可能为空），它是后续待处理链表的头节点
- 交换传入链表的
head和head.next,此时head.next交换后链表的头节点 - 将后续待处理链表处理完成后返回的头节点连接到
head节点之后（因为此时head节点为交换后的第二个节点） - 返回本次交换后的头节点即可
代码如下：
// 将传入链表的第一，第二个节点交换，并递归处理后续链表 function swap(head){ // 如果链表节点数量不够2个，直接返回 if(head===null || head.next===null) return head; // 记录后续链表的头节点 const nextHead = head.next.next, vhead = new ListNode(0); // 记录要返回的头节点 vhead.next = head.next; // 交换两个节点 head.next.next = head; // 将后续链表处理后返回的头节点连接到交换后第二个节点的后面 head.next = swap(nextHead) // 返回交换后的头节点 return vhead.next; } var swapPairs = function(head) { // 调用swap完成链表节点两两交换 return swap(head); }; 复制代码
题解2
直接在链表遍历过程中处理
- 如果输入链表节点数量不足两个，返回原链表
- 当剩余待处理链表中有两个节点的时候，记录第三个节点（为后续待处理链表的头节点）
- 交换本次处理的两个节点，并将交换后的头节点连接到结果链表末尾
- 更新第一个节点指针为后续待处理链表的头节点
- 判断是否有第二个节点，如果有，更新第二个节点指针为第二个节点，否则指向
null - 当链表不足两个的时候，判断第一个节点指针是否指向真实节点，如果是，将它连接在结果链表末尾
- 返回结果链表头节点即可
代码如下：
var swapPairs = function(head) { // 如果输入链表节点数量不足两个，返回原链表 if(head===null || head.next===null) return head; const vhead = new ListNode(0); let pre = vhead, tail = head, next = head.next; // 当剩余链表有两个节点的时候 while(tail&&next){ // 记录第三个节点 const nextHead = next.next; // 交换两个节点 next.next = tail; tail.next = null; // 将交换后的头节点连接到结果链表末尾 pre.next = next; // 更新指针 pre = tail; tail = nextHead; next = tail?tail.next:null; } // 如果最后tail指针指向真实节点，将其连接到结果链表末尾 if(tail) pre.next = tail; // 返回结果链表头节点 return vhead.next; }; 复制代码
至此我们就完成了 leetcode-24-两两交换链表中的节点
如有任何问题或建议，欢迎留言讨论！
