SimuVedaAlgorithms Lab Open in the lab

Lists, stacks & queues / Intermediate

Merge Two Sorted Linked Lists Visualizer

A dummy node gives the merged list a fixed start. tail points at its last node. Each step links the smaller of the two front nodes after tail and moves on. When one list ends, link the rest of the other.

Start the Merge Two Sorted Linked Lists simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n + m)
Average timeO(n + m)
Worst timeO(n + m)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Left: the first list (1 → 3 → 5 → 7). Right: the second (2 → 4 → 6). tail starts at a dummy node.
  2. Compare 1 and 2.
  3. 1 is smaller: link it after the dummy.
  4. Move tail to 1.
  5. Compare 3 and 2.
  6. 2 is smaller: link it after 1.
  7. Move tail to 2.
  8. Compare 3 and 4.
  9. 3 is smaller: link it after 2.
  10. Move tail to 3.
  11. Compare 5 and 4.
  12. 4 is smaller: link it after 3.
  13. Move tail to 4.
  14. Compare 5 and 6.
  15. 5 is smaller: link it after 4.
  16. Move tail to 5.
  17. Compare 7 and 6.
  18. 6 is smaller: link it after 5.
  19. Move tail to 6.
  20. One list is used up. Link the rest (7 onward) after 6.
  21. Done. Return dummy.next: 1 → 2 → 3 → 4 → 5 → 6 → 7.

Try it with your own input →

Merge two sorted linked lists in Java, Python, C++, C and JavaScript

ListNode merge(ListNode a, ListNode b) {
  ListNode dummy = new ListNode(0), tail = dummy;
  while (a != null && b != null) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = (a != null) ? a : b;
  return dummy.next;
}
def merge(a, b):
    dummy = tail = ListNode(0)
    while a and 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 if a else b
    return dummy.next
ListNode* merge(ListNode* a, ListNode* b) {
  ListNode dummy(0); ListNode* tail = &dummy;
  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 dummy.next;
}
struct ListNode* merge(struct ListNode* a, struct ListNode* b) {
  struct ListNode dummy = { 0, NULL }, *tail = &dummy;
  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 dummy.next;
}
function merge(a, b) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a !== null ? a : b;
  return dummy.next;
}

In an interview

LeetCode 21, Merge Two Sorted Lists: splice two sorted linked lists into one sorted list without new nodes.

The dummy node removes the "is this the first node?" special case. Nothing is copied: only next pointers change, so extra space is O(1).

More lists, stacks & queues