Merge Two Sorted Linked Lists

Given two sorted linked lists, merge them into a single sorted linked list and return its head.

Difficulty:

JavaScript Solution

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

Explanation: Iteratively compare nodes of both lists and build a new sorted list.

⏱ O(n + m) | 💾 O(1)

Java Solution

class Solution {
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while(l1 != null && l2 != null){
      if(l1.val < l2.val){ tail.next = l1; l1 = l1.next; }
      else{ tail.next = l2; l2 = l2.next; }
      tail = tail.next;
    }
    tail.next = l1 != null ? l1 : l2;
    return dummy.next;
  }
}

Explanation: Iteratively merge using a dummy node and compare node values.

⏱ O(n + m) | 💾 O(1)

Python Solution

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and l2:
        if l1.val < l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Explanation: Compare nodes iteratively and build a merged list.

⏱ O(n + m) | 💾 O(1)

Console

🎬 Share Your Coding Journey

Thumbnail Templates

Merge Two Sorted Linked Lists