Merge Two Sorted List

• Easy
• keyword: Pattern, Math
• 类似: insertion sort lists, merge k lists

将2个排好序的list合并

idea 1

• 我一开始没看到是sorted, 所以我就用priorityQueue保存所有的, 然后一个个poll出来. 结果自然是很慢的.

idea 2

• 就是merge sort. 只是从array变成了list
• 代码如下:

  public ListNode mergeTwoLists(ListNode l1, ListNode 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;
    }
  }