LeetCode 题解:24. 两两交换链表中的节点,迭代,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 08 月 06 日
LeetCode题解:24. 两两交换链表中的节点,迭代,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs/



解题思路:



  1. 假设链表编号从1开始,按照1,3,5,7...的顺序遍历链表。

  2. 每次循环将两个节点调换,假设链表1->2->3->4,调换一次后就是2->1->3->4,以此类推。

  3. 需要注意的是,调换实际需要3个节点参与,因此在第一次调换时,需要创建一个伪节点参与。

  4. 调换的顺序是1->3,2->1,-1->2。



```javascript []

/**

* @param {ListNode} head

* @return {ListNode}

*/

// 以链表1->2->3->4为例。

var swapPairs = function (head) {

// 创建一个伪节点,用来淡妆第一次调换时的prevNode,以及输出最终的结果

let dummyNode = new ListNode(-1);

// 初始状态dummyNode.next指向head,如果当前链表长度小于2,则直接返回head。

dummyNode.next = head;

// 由于节点指向的交换,实际上由3个节点参与。

// 因此对于第一次交换,需要提供一个prevNode参与。

let prevNode = dummyNode; // 初始状态为-1

let currentNode = head; // 初始状态为1

let nextNode; // 不需要设置初始值,进入循环后,会设置初始状态为2



// 遍历链表,当前例子的链表为-1->1->2->3->4,-1为dummyNode。

// 注意:while循环中的注释,都指的是第一次遍历。

// 对于第n次遍历而言,prevNode是链表的真实节点,不再是dummyNode。

while (currentNode && currentNode.next) {

nextNode = currentNode.next; // 获取要调换的下一个节点,即为2



// 经过如下调换之后,链表变为了-1->2->1->3->4。

currentNode.next = nextNode.next; // 1->3

nextNode.next = currentNode; // 2->1

prevNode.next = nextNode; // -1->2



// currentNode即节点1,也就是下一次调换的prevNode.

// 此时需要注意的是,prevNode确实被替换了。

// 而dummyNode还是旧的prevNode(-1),其next指向的是第一次调换后的头节点,即2.

prevNode = currentNode;

// 将链表向前移动

currentNode = currentNode.next;

}



// 此时dummyNode.next其实指向的是是头两个节点调换后,真实的头节点。

// 当链表的节点数小于2时,不会进入循环,直接返回的是当前节点head

return dummyNode.next;

};

```



发布于: 2020 年 08 月 06 日 阅读数: 23
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:24. 两两交换链表中的节点,迭代,JavaScript,详细注释