leetcode21：合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

附leetcode地址：leetcode

解答：

确定解题的数据结构： 单链表

确定解题思路： 从链表头开始比较，l1 与 l2 是有序递增的，所以比较 l1.val 与 l2.val 的较小值就是合并后链表的最小值，次小值就是小节点的 next.val 与大节点的 val 比较的较小值，依次递归，直到递归到 l1 l2 均为 null

画图实现： 画图帮助理解一下

确定边界条件： 当递归到任意链表为 null ，直接将 next 指向另外的链表即可，不需要继续递归了

代码实现：

function mergeTwoLists(l1, l2) {
    if(l1 === null) {
        return l2
    }
    if(l2 === null) {
        return l1
    }
    if(l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists(l2.next, l1)
        return l2
    }
}

我这个就稍微麻烦了点

var mergeTwoLists = function(l1, l2) {
    let res = new List();
    while(l1 !== null && l2 !== null){
        if(l1.element < l2.element){
            res.append(l1.element);
            l1 = l1.next;
        }else{
            res.append(l2.element);
            l2 = l2.next;
        }
    }
    let temp = !l1 ? l2 : l1;
    while(temp){
        res.append(temp.element);
        temp = temp.next;
    }
    return res;
};

var mergeTwoLists = function(l1, l2) {
  if (l1 === null) {
    return l2
  } else if (l2 === null) {
    return l1
  } else if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
};

虚拟节点+ 迭代

  function ListNode(val, next) {
      this.val = (val===undefined ? 0 : val)
      this.next = (next===undefined ? null : next)
 }

var mergeTwoLists = function(l1, l2) {
    
    let preHead = new ListNode(-1);
    let cur = preHead;

    while(l1 && l2){
        if(l1.val < l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    cur.next = l1 || l2;

    return preHead.next;
};

 const merge = (l1, l2) => {
  let temp1 = l1.head
  let temp2 = l2.head
  let list = new List()
  while (temp1 || temp2) {
    if (!temp1) {
      list.add(temp2.value)
      temp2 = temp2.next
    } else if (!temp2) {
      list.add(temp1.value)
      temp1 = temp1.next
    } else if (temp1.value >= temp2.value) {
      list.add(temp2.value)
      temp2 = temp2.next
    } else {
      list.add(temp1.value)
      temp1 = temp1.next
    }
  }
  return list
}

function merge_link1(head1, head2) {
  if (!head1) return head2
  if (!head2) return head1

  let merge_head = null
  let merge_tail = null
  let min_data = null

  let curr1 = head1
  let curr2 = head2

  while (curr1 && curr2) {
    if (curr1.data < curr2.data) {
      min_data = curr1.data
      curr1 = curr1.next
    } else {
      min_data = curr2.data
      curr2 = curr2.next
    }

    if (!merge_head) {
      merge_head = new Node(min_data)
      merge_tail = merge_head
    } else {
      const new_node = new Node(min_data)
      merge_tail.next = new_node
      merge_tail = new_node
    }
  }

  // 循环结束后，还有某个链表还有值
  let rest_link = null
  if (curr1) {
    rest_link = curr1
  }
  if (curr2) {
    rest_link = curr2
  }

  // while (rest_link) {
  //   merge_tail.next = rest_link
  //   merge_tail = rest_link
  //   rest_link = rest_link.next
  // }
  merge_tail.next = rest_link
  return merge_head
}

var mergeTwoLists = function(l1, l2) {
  let head = new ListNode()
  let cur = head

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1 // 指向目标节点
      l1 = l1.next // 移动到下一个节点
    } else {
      cur.next = l2
      l2 = l2.next
    }

    cur = cur.next
  } 
  // 处理l1或者l2还未遍历完的场景
  cur.next = l1 || l2

  return head.next
};

var mergeTwoLists = function (l1, l2) {
  let p1 = new ListNode(0)
  let end = p1
  while (l1 && l2) {
    if (l1.val >= l2.val) {
      end.next = l2
      l2 = l2.next
    } else {
      end.next = l1
      l1 = l1.next
    }
    end = end.next
  }
  end.next = l1 ? l1 : l2
  return p1.next
}

解答：

确定解题的数据结构： 单链表

确定解题思路： 从链表头开始比较，l1 与 l2 是有序递增的，所以比较 l1.val 与 l2.val 的较小值就是合并后链表的最小值，次小值就是小节点的 next.val 与大节点的 val 比较的较小值，依次递归，直到递归到 l1 l2 均为 null

画图实现： 画图帮助理解一下

确定边界条件： 当递归到任意链表为 null ，直接将 next 指向另外的链表即可，不需要继续递归了

代码实现：
function mergeTwoLists(l1, l2) {
    if(l1 === null) {
        return l2
    }
    if(l2 === null) {
        return l1
    }
    if(l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists(l2.next, l1)
        return l2
    }
}

这个图片是用什么画图工具做出来的？

var mergeTwoLists = function (l1, l2) {
    let prev = new ListNode();
    let p1 = l1, p2 = l2;
    let current = prev;
    while (p1 && p2) {
        if (p1.val > p2.val) {
            current.next = new ListNode(p2.val);
            p2 = p2.next;
        } else {
            current.next = new ListNode(p1.val);
            p1 = p1.next;
        }
        current = current.next;
    }
    current.next = p1 ? p1 :p2;
    return prev.next;
};

题目地址(21. 合并两个有序链表)

https://leetcode-cn.com/problems/merge-two-sorted-lists

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

前置知识

公司

阿里
字节
腾讯
amazon
apple
linkedin
microsoft

公司

阿里、字节、腾讯

思路

本题可以使用递归来解，将两个链表头部较小的一个与剩下的元素合并，并返回排好序的链表头，当两条链表中的一条为空时终止递归。

关键点

掌握链表数据结构
考虑边界情况

代码

语言支持：CPP，JS

CPP Code:

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode head, *tail = &head;
        while (a && b) {
            if (a->val <= b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return head.next;
    }
};

JS Code:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

复杂度分析

M、N 是两条链表 l1、l2 的长度

时间复杂度：$O(M+N)$
空间复杂度：$O(M+N)$

扩展

你可是使用迭代的方式求解么？

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  let dummy = new ListNode(null);
  let temp = dummy;
  let node1 = l1;
  let node2 = l2;
  while(node1 || node2){
    if(!node1){
      temp.next = node2;
      break;
    }
    if(!node2){
      temp.next = node1;
      break;
    }
    if(node1.val <= node2.val){
      temp.next = node1;
      node1 = node1.next;
    }else{
      temp.next = node2;
      node2 = node2.next;
    }
    temp = temp.next;
  }

  return dummy.next;
};

/**
 * 重新创建一个链表
 */
 var mergeTwoLists = function(l1, l2) {
    if(l1===null) return l2;
    if(l2===null) return l1;
    let curL1 = l1;
    let curL2 = l2;
    let head = new ListNode(0);
    let cur = head;
    while(curL1!==null&&curL2!==null) {
        if(curL1.val<=curL2.val) {
            cur.next = curL1;
            curL1 = curL1.next;
        } else {
            cur.next = curL2;
            curL2 = curL2.next;
        }
        cur = cur.next;
    }
    cur.next = curL1===null?curL2:curL1;
    return head.next;
};

const chain1 = {
  val: 1,
  next: {
    val: 3,
    next: {
      val: 5,
      next: null,
    },
  },
};
const chain2 = {
  val: 2,
  next: {
    val: 4,
    next: {
      val: 6,
      next: null,
    },
  },
};
function merge(l1: any, l2: any) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = merge(l1.next, l2);
    return l1;
  } else {
    l2.next = merge(l1, l2.next);
    return l2;
  }
}
merge(chain1, chain2);
console.log("chain1", chain1);
console.log("chain2", chain2);

Navigation Menu

Repository navigation

leetcode21：合并两个有序链表 #11

题目地址(21. 合并两个有序链表)

题目描述

前置知识

公司

公司

思路

关键点

代码

扩展

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

leetcode21：合并两个有序链表 #11

Description

Activity

sisterAn commented on Apr 9, 2020

liwuhou commented on Apr 11, 2020

13001920223 commented on Apr 23, 2020

fengmiaosen commented on Jun 16, 2020

xyj626553989 commented on Jul 3, 2020

Been101 commented on Jul 15, 2020

qianlongo commented on Aug 15, 2020

gloomyKevin commented on Sep 8, 2020

wufeicris commented on Nov 8, 2020

AnranS commented on Nov 16, 2020

azl397985856 commented on Mar 3, 2021

题目地址(21. 合并两个有序链表)

题目描述

前置知识

公司

公司

思路

关键点

代码

扩展

in-vane commented on Mar 25, 2021

xllpiupiu commented on Oct 1, 2021

fengjinlong commented on Dec 4, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions