24-两两交换链表中的节点
标签：递归 链表
题目信息
题目地址： 24. 两两交换链表中的节点
题目内容：
javascript
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
示例1图片如下：
题解
解法一
思路：
设置虚拟头节点
dummyHead，它的next指向head，遍历链表，设置遍历节点curNode，默认指向dummyHead当
curNode.next和curNode.next.next都存在时，交换两个的位置直到
curNode.next或者curNode.next.next为null时，结束循环
图解如下，看图会好理解一点
代码实现：
javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
// 使用虚拟头节点
const dummyHead = new ListNode(0, head)
let curNode = dummyHead
while(curNode.next !== null && curNode.next.next !== null) {
// 暂时保存curNode.next节点 为了交换时使用
const temp1 = curNode.next
// 保存要交换的第二个节点的next节点 比如节点2的next/节点4的next
const temp2 = curNode.next.next.next
curNode.next = curNode.next.next
curNode.next.next = temp1
temp1.next = temp2
// curNode.next.next.next = temp2 和上面的写法效果一致
curNode = curNode.next.next
}
return dummyHead.next
};
解法二
思路：
使用
递归，理解了方法一后，可以轻松写出递归版本的代码
代码实现：
javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
// 使用虚拟头节点
const dummyHead = new ListNode(0, head)
let curNode = dummyHead
const swapNodesInPairs = (curNode) => {
// 终止递归
if(curNode.next === null || curNode.next.next === null) return
const temp1 = curNode.next
const temp2 = curNode.next.next.next
curNode.next = curNode.next.next
curNode.next.next = temp1
temp1.next = temp2
return swapNodesInPairs(curNode.next.next)
}
swapNodesInPairs(curNode)
return dummyHead.next
};