LeetCode 题解:21. 合并两个有序链表,迭代,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 08 月 09 日

原题链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/



解题思路:



  1. 用双指针同时遍历两个链表。

  2. l1.val<l2.val时,将l1存入新链表,l1向前移动一位

  3. l2.val<l1.val时,将l2存入新链表,l2向前移动一位

  4. l1.val=l2.val时,将l1和l2分别存入新链表,l1和l2都向前移动一位



/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function (l1, l2) {
// 创建一个伪节点,排序后的新链表的首节点会存储在dummyNode.next中
let dummyNode = new ListNode(-1);
// 存储新链表的节点,会随着新链表的连接而重新赋值
// 新链表的首节点存储为dummyNode,避免在存储新链表时,首节点为空的问题
let newListNode = dummyNode;
function moveNode(node) {
// 将排序后的当前节点连接到新链表
newListNode.next = node;
newListNode = newListNode.next;
// 当前链表向前移动一位,并将移动后的结果返回,更新旧链表节点
return (node = node.next);
}
// 同时遍历两个链表,都完成遍历的时候退出
while (l1 || l2) {
// 考虑两种条件
// 1. 当l2为空时,直接将l1存入新链表
// 2. 当l1.val < l2.val时,将l1存入新链表,如此循环即可完成链表的排序
// 3. 判断l1.val < l2.val之前,需要确认l1是否存在,否则可能出错
if (!l2 || (l1 && l1.val < l2.val)) {
l1 = moveNode(l1);
}
// 此处判断与上一级判断相反
else if (!l1 || (l2 && l2.val < l1.val)) {
l2 = moveNode(l2);
}
// 当l1.val === l2.val时,两个链表的节点都需要存入新链表
else if (l1.val === l2.val) {
l1 = moveNode(l1);
l2 = moveNode(l2);
}
}
// dummyNode.next指向的是新链表的第一个节点
// 因此此处返回的就是新链表。
return dummyNode.next;
};



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

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:21. 合并两个有序链表,迭代,JavaScript,详细注释