← Index

Linked List

Merge Two Sorted ListsEasy

Merge two sorted linked lists into one sorted linked list by splicing together the existing nodes (don't create new nodes for the values).

Examples

Approach

This is the merge step from Merge Sort, applied to linked lists instead of arrays. Walk both lists with two pointers, and at each step attach whichever current node has the smaller value to the result, advancing that list's pointer. A dummy head node sidesteps the awkward 'what's the first node of the result?' special case — just return dummy.next when done. Once one list runs out, the other's remaining nodes are already sorted, so attach them directly.

Complexity — best & worst case

Code

// Merge two sorted linked lists into one sorted linked list by
// splicing their existing nodes together (no new nodes for values).

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

function buildList(values) {
  const dummy = new ListNode(0);
  let current = dummy;
  for (const v of values) {
    current.next = new ListNode(v);
    current = current.next;
  }
  return dummy.next;
}

function toArray(head) {
  const out = [];
  while (head) {
    out.push(head.value);
    head = head.next;
  }
  return out;
}

// --- Approach: dummy head + two pointers, same merge step as merge sort ---
// A "dummy" node avoids special-casing "what's the head of the result?" —
// we just return dummy.next at the end.
function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(0);
  let current = dummy;

  while (list1 && list2) {
    if (list1.value <= list2.value) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }
    current = current.next;
  }

  // one list may have leftovers — they're already sorted, just attach them
  current.next = list1 || list2;

  return dummy.next;
}

// --- Example Usage ---
const merged = mergeTwoLists(buildList([1, 2, 4]), buildList([1, 3, 4]));
console.log(toArray(merged)); // [1,1,2,3,4,4]

console.log(toArray(mergeTwoLists(buildList([]), buildList([0])))); // [0]