leetcode21：合并两个有序链表

[sisterAn]

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

示例：

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

附leetcode地址：leetcode

[sisterAn]

解答：

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

确定解题思路： 从链表头开始比较，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
    }
}

[liwuhou]

我这个就稍微麻烦了点

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;
};

[13001920223]

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
  }
};

[fengmiaosen]

虚拟节点+ 迭代

  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;
};

[xyj626553989]

 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
}

[Been101]

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
}

[qianlongo]

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
};

[gloomyKevin]

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
}

[wufeicris]

解答：

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

确定解题思路： 从链表头开始比较，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
    }
}

解答：

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

确定解题思路： 从链表头开始比较，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
    }
}

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

[AnranS]

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;
};

[azl397985856]

题目地址(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 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。