Merge Two Sorted Linked Lists in DSA Javascript - Build from Scratch

Merge Two Sorted Linked Lists

📖 Scenario: You are working on a contact app that keeps two separate lists of contacts sorted by their names. You want to merge these two sorted lists into one sorted list so that you can display all contacts in order.

🎯 Goal: Build a program that merges two sorted linked lists into one sorted linked list.

📋 What You'll Learn

Create two sorted linked lists using the provided Node class

Create a helper variable to track the head of the merged list

Write the core logic to merge the two sorted linked lists

Print the merged linked list in the format: value1 -> value2 -> ... -> null

💡 Why This Matters

🌍 Real World

Merging sorted lists is common in contact apps, calendars, and any app that combines sorted data from multiple sources.

💼 Career

Understanding linked lists and merging algorithms is important for software engineering roles that involve data structures and algorithmic problem solving.

1

Create Two Sorted Linked Lists

Create a class called Node with a constructor that takes value and sets this.value and this.next to null. Then create two sorted linked lists called list1 and list2 with these exact values: list1 contains nodes with values 1, 3, 5 and list2 contains nodes with values 2, 4, 6. Link the nodes properly.

DSA Javascript

// Create Node class and two sorted linked lists list1 and list2
// Your code here

Hint

Start by defining the Node class. Then create nodes for each list and link them using the next property.

2

Create a Dummy Head for Merged List

Create a variable called dummy and set it to a new Node with value 0. Then create a variable called current and set it equal to dummy. This will help us build the merged list.

DSA Javascript

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

// Create list1: 1 -> 3 -> 5 -> null
const list1 = new Node(1);
list1.next = new Node(3);
list1.next.next = new Node(5);

// Create list2: 2 -> 4 -> 6 -> null
const list2 = new Node(2);
list2.next = new Node(4);
list2.next.next = new Node(6);

// Create dummy head and current pointer
// Your code here

Hint

Use a dummy node to simplify merging. Set current to point to this dummy node.

3

Merge the Two Sorted Lists

Write a while loop that runs while both list1 and list2 are not null. Inside the loop, compare list1.value and list2.value. If list1.value is less than or equal to list2.value, set current.next to list1 and move list1 to list1.next. Otherwise, set current.next to list2 and move list2 to list2.next. Then move current to current.next. After the loop, set current.next to whichever list is not null (list1 or list2).

DSA Javascript

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

// Create list1: 1 -> 3 -> 5 -> null
const list1 = new Node(1);
list1.next = new Node(3);
list1.next.next = new Node(5);

// Create list2: 2 -> 4 -> 6 -> null
const list2 = new Node(2);
list2.next = new Node(4);
list2.next.next = new Node(6);

const dummy = new Node(0);
let current = dummy;

// Merge the two lists
// Your code here

Hint

Use two pointers to traverse both lists. Attach the smaller node to current.next and move pointers forward.

4

Print the Merged Linked List

Create a variable called result as an empty string. Create a variable called node and set it to dummy.next. Use a while loop to traverse the merged list until node is null. Inside the loop, append node.value and ' -> ' to result. Move node to node.next. After the loop, append 'null' to result. Finally, print result using console.log.

DSA Javascript

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

// Create list1: 1 -> 3 -> 5 -> null
const list1 = new Node(1);
list1.next = new Node(3);
list1.next.next = new Node(5);

// Create list2: 2 -> 4 -> 6 -> null
const list2 = new Node(2);
list2.next = new Node(4);
list2.next.next = new Node(6);

const dummy = new Node(0);
let current = dummy;

let l1 = list1;
let l2 = list2;

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

current.next = l1 !== null ? l1 : l2;

// Print the merged list
// Your code here

Hint

Traverse the merged list starting from dummy.next. Build a string with each node's value followed by ' -> '. End with 'null'. Print the string.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. To find the largest element in both lists

B. To reverse both linked lists

C. To create a new sorted linked list containing all elements from both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merging process

   Merging means combining two lists into one while keeping the order sorted.

2. Step 2: Identify the goal of merging sorted lists

   The goal is to create a new sorted list that contains all elements from both lists without changing their order.

3. Final Answer:

   To create a new sorted linked list containing all elements from both lists -> Option C

4. Quick Check:

   Merging = combining sorted lists [OK]

Hint: Merging means combining sorted lists into one sorted list [OK]

Common Mistakes:

• Thinking merging reverses the lists
• Confusing merging with finding max element
• Assuming duplicates are removed automatically

2. Which of the following is the correct way to start merging two sorted linked lists in JavaScript?

easy

A. let dummy = new ListNode(0); let current = dummy;

B. let dummy = new ListNode(); let current = dummy.next;

C. let dummy = 0; let current = dummy;

D. let current = null; let dummy = current;

Solution

1. Step 1: Initialize a dummy node correctly

   We create a dummy node with a value (usually 0) to start the merged list.

2. Step 2: Set a pointer to track the current node

   We set current to dummy to build the merged list from dummy onwards.

3. Final Answer:

   let dummy = new ListNode(0); let current = dummy; -> Option A

4. Quick Check:

   Dummy node initialization = let dummy = new ListNode(0); let current = dummy; [OK]

Hint: Start with dummy node and current pointer for easy list building [OK]

Common Mistakes:

• Using primitive 0 instead of ListNode object
• Swapping dummy and current incorrectly
• Setting current or dummy to null initially

3. What will be the merged linked list after running the following code?

function ListNode(val, next = null) { this.val = val; this.next = next; }

let l1 = new ListNode(1, new ListNode(3, new ListNode(5)));
let l2 = new ListNode(2, new ListNode(4, new ListNode(6)));

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

let merged = mergeTwoLists(l1, l2);

let result = [];
while (merged) {
  result.push(merged.val);
  merged = merged.next;
}
console.log(result);

medium

A. [1, 3, 5, 2, 4, 6]

B. [1, 2, 3, 4, 5, 6]

C. [2, 4, 6, 1, 3, 5]

D. [6, 5, 4, 3, 2, 1]

Solution

1. Step 1: Trace the merging loop

   Compare nodes: 1 < 2, add 1; 3 > 2, add 2; 3 < 4, add 3; 5 > 4, add 4; 5 < 6, add 5; then add remaining 6.

2. Step 2: Collect merged list values

   The merged list values in order are [1, 2, 3, 4, 5, 6].

3. Final Answer:

   [1, 2, 3, 4, 5, 6] -> Option B

4. Quick Check:

   Sorted merge result = [1, 2, 3, 4, 5, 6] [OK]

Hint: Compare heads, pick smaller, move pointer, repeat [OK]

Common Mistakes:

• Appending entire list instead of node by node
• Not updating current pointer after adding node
• Mixing order of nodes in merged list

4. Identify the bug in this merge function and select the fix:

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

medium

A. Initialize dummy with null instead of 0

B. Add check for null before comparing l1.val and l2.val

C. Remove current = current.next inside the loop

D. Change while condition to 'while (l1 && l2)'

Solution

1. Step 1: Analyze the while loop condition

   The loop uses '||' which allows l1 or l2 to be null, causing errors when accessing val.

2. Step 2: Fix the loop condition

   Changing the condition to 'while (l1 && l2)' ensures both lists have nodes before accessing val.

3. Final Answer:

   Change while condition to 'while (l1 && l2)' -> Option D

4. Quick Check:

   Loop condition with && prevents null pointer errors [OK]

Hint: Use && in loop condition to ensure both nodes exist before access [OK]

Common Mistakes:

• Using || instead of && in loop condition without null checks
• Forgetting to move current pointer
• Initializing dummy with wrong value type

5. Given two sorted linked lists where one is empty and the other is 1 -> 2 -> 3 -> null, what is the merged list?

medium

A. 1 -> 2 -> 3 -> null

B. Error due to empty list

C. 3 -> 2 -> 1 -> null

D. null

Solution

1. Step 1: Understand merging with an empty list

   If one list is empty, the merged list is just the other list unchanged.

2. Step 2: Apply this to given lists

   Since one list is empty and the other is 1 -> 2 -> 3 -> null, the merged list is 1 -> 2 -> 3 -> null.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Merging with empty list returns the non-empty list [OK]

Hint: Empty list merged with sorted list returns the sorted list [OK]

Common Mistakes:

• Assuming error occurs when one list is empty
• Reversing the non-empty list mistakenly
• Returning null instead of the non-empty list