初级-链表-合并两个有序链表(JavaScript)

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

示例:

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

思路:

方法很多,之前写过迭代法,这次写写递归法吧。

若其中某条链表为空,那必然是返回另一条不为空的了。

比较两条链表的头节点的大小,将较小者作为新链表的头节点,然后递归调用方法即可。

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

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 13:15
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务