给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
[0, 100]
内0 <= Node.val <= 100
/**
* 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}
*/
// 迭代法
// 主要修改的几个指针(注意顺序不要变):
// 1.要交换的第一个节点的上一个节点的下一个节点指针,变为第二个
// 2.要交换的第一个节点的下一个节点指针,变为第三个
// 3.要交换的第二个节点的下一个节点指针,变为第一个
var swapPairs = function(head) {
if(!head || !head.next){
return head;
}
// 创建一个空节点
let prev = new ListNode(0);
// 将空节点的下一个指向头结点
prev.next = head;
// 复制创建的节点
let res = prev;
// while 迭代
while(prev.next && prev.next.next){
// 先获取第一个节点
let start = prev.next;
// 获取第一个节点的下一个
let end = prev.next.next
// 将头节点的下一个节点指向第二个节点
prev.next = end;
// 将第一个节点的下一个指向第三个节点
start.next = end.next;
// 将第二个节点的下一个指向第一个节点,这里注意顺序,因为上面会用到 end.next,下面又会进行修改,先使用,后修改
end.next = start;
// 去到下一个节点迭代
prev = start;
}
// 返回创建的节点的下一个即为最终结果
return res.next;
};