Linked List Merge

Merging Two Linked Lists

Merging two linked lists involves combining the nodes of both lists into one sorted list. This is typically done using a two-pointer approach where we repeatedly compare the heads of both lists and append the smaller node to the result.

This operation is especially useful when both input lists are already sorted. The result is also a sorted list without requiring additional sorting operations.

Tip: Merging is efficient when input lists are already sorted and doesn’t require extra space beyond a few pointers.

Steps to Merge

  1. Create a dummy node to act as the starting point of the merged list
  2. Use a pointer (current) to track the last node in the merged list
  3. While both lists are non-empty, compare the current nodes
  4. Attach the smaller node to the merged list and move that list's pointer forward
  5. Once one list is exhausted, link the remaining part of the other list to the merged list
  6. Return the node next to dummy as the head of the merged list

Edge Cases

  • Both lists are empty
  • One list is empty
  • All nodes in one list are smaller than the other
  • Lists have overlapping values
  • Input lists are not sorted (may result in unsorted merged list)

Best Practices

  • Ensure both input lists are sorted before merging
  • Always use a dummy node to simplify edge case handling
  • Track edge conditions where one list might be empty
  • Avoid modifying original input lists if immutability is required
  • Consider recursive merging for a concise approach (at the cost of stack space)

Visualize merging two sorted linked lists

List 1
List 2
Merged
Pointer

List 1

Generate List 1 to begin

List 2

Generate List 2 to continue

Merged List

Generate both lists and merge them

Test Your Knowledge Before Moving Forward!

Merging Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Linked List Merging Implementation

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

function mergeLists(l1, l2) {
  const dummy = new Node(0);
  let current = dummy;

  while (l1 && l2) {
    if (l1.data < l2.data) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }

  current.next = l1 || l2;
  return dummy.next;
}

Explore Other Operations

Insertion

Deletion

Traversal

Comparison

Searching

Reverse