#21 Leetcode.21 Merge Two Sorted Lists

tags: Linked list Easy

Problem

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Sample Input & Output

example 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

example 2

Input: list1 = [], list2 = []
Output: []

example 3

Input: list1 = [], list2 = [0]
Output: [0]

Optimal Space & Time Complexity

---

Solutions

Most voted solution

var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode();
    let currTail = dummy;
    while(l1 && l2) {
        if(l1.val > l2.val) {
            currTail.next = l2;
            l2 = l2.next;
        } else {
            currTail.next = l1;
            l1 = l1.next;
        }
        currTail = currTail.next;
    }
    currTail.next = l1 || l2;
    
    return dummy.next;
};

---

Everyone's

Totally misunderstood listed list but pass the rest…

東

var mergeTwoLists = function(list1, list2) {
    let head = null;
    if (!list1 && list2) return list2;
    if (!list2 && list1) return list1;
    if (!list1 && !list2) return null;
    
    if (list1.val < list2.val){
         head = new ListNode(list1.val)
         list1 = list1.next;
    } else {
         head = new ListNode(list2.val)
         list2 = list2.next;
    }
    
    let currNode = head;
    
    while(list1 !== null && list2 !== null){
       if (list1.val < list2.val){
         currNode.next = new ListNode(list1.val)
         list1 = list1.next;
       } else {
         currNode.next = new ListNode(list2.val)
         list2 = list2.next;
       }
       currNode = currNode.next;
    }
    
    if (list1 !== null) currNode.next = list1;
    if (list2 !== null) currNode.next = list2;
    
    return head;
};

Fail the test and would like some discussion

Sorry… but please explain.

Hao

/**
 * Why it fails the tests?
 */

var mergeTwoLists = function (list1, list2) {
  const getHeadNode = () => {
    if (!list1) return list2;
    if (!list2) return list1;
    return list1.value <= list2.value ? list1 : list2;
  };
  const headNode = getHeadNode();
  if (headNode) {
    let curListNode = headNode;
    let otherListNode = headNode === list1 ? list2 : list1;

    while (otherListNode) {
      if (!curListNode.next || curListNode.next.value > otherListNode.value) {
        const newCurListNextNode = otherListNode;
        otherListNode = curListNode.next;
        curListNode.next = newCurListNextNode;
      };
      curListNode = curListNode.next;
    }
  }
  return headNode;
};

Raiy

var mergeTwoLists = function(list1, list2) {
    // time:O(m+n)  space:O(m+n) n = list1 length, m = list2 length
    if(!list1 || !list2){
        return list1 ? list1:list2
    }
        
    let mergedList = new ListNode(0,null);
    let currentNode = mergedList;
    
    while(list1 && list2){
        if(list1.val < list2.val){
            currentNode.next = list1
            list1 = list1.next
        }else{
            currentNode.next = list2
            list2 = list2.next
        }
        currentNode = currentNode.next
    }
    
    if(!list1){
        currentNode.next = list2
    }else if(!list2){
        currentNode.next = list1
    }
    
    return mergedList.next
};

YC

• Usage of ??

/**
 * time: O(m+n) - where m is the number of nodes in the list1, n is the number of nodes in the list2 
 * space: O(m+n) - where m is the number of nodes in the list1, n is the number of nodes in the list2 
 */
var mergeTwoLists = function(list1, list2) {
    if(!list1) return list2;
    if(!list2) return list1;
    
    const dummy = [];
    let curr = dummy;
    
    while(list1 && list2){
        if(list1.val < list2.val){
            curr.next = list1;
            list1 = list1.next;
        }
        else{
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    curr.next = list1 ?? list2;
    return dummy.next;
};

Very similar to the most voted solution

Becky

//time: O(n) | space: O(n)
var mergeTwoLists = function(list1, list2) {
    const head = new ListNode();
    currentNode = head;
    while( list1 && list2){
        if( list1.val >= list2.val){
            currentNode.next = list2;
            list2 = list2.next;
        }else{
            currentNode.next = list1;
            list1 = list1.next;
        }
        currentNode = currentNode.next
    }
    //假設其中一個list先null
    if (list1){
        currentNode.next = list1
    }else{
        currentNode.next = list2
    }
    return head.next
};

月 (Very similar to best approach)

var mergeTwoLists = function(l1, l2) {
    // Time O(n) Space O(n)
    const result = new ListNode(0);
    let pointer = result; // Why pointer can reaction to result?
    while(l1 && l2){
        if(l1.val < l2.val){
            pointer.next = l1;  // Why not l1.val?
            l1 = l1.next;
        } else {
            pointer.next = l2;
            l2 = l2.next
        }
        pointer = pointer.next;
    }
    pointer.next = l1 || l2;
    return result.next
};

---

Supplement / Discussion

Usage of dummy

• Initiate head and tail
• Make pointer from dummy
• Handle edge case of null input

let dummy = new ListNode();
let currTail = dummy;

// some work

return dummy.next;

Usage of ??