Merge Two Sorted Linked Lists in DSA Go - Execution Trace

Concept Flow - Merge Two Sorted Linked Lists

Start with two sorted lists

↓

Compare heads of both lists

↓

Smaller node

→Add to merged list

↓

Move pointer in that list

↓

Repeat until one list empty

↓

Attach remaining nodes of other list

↓

Return merged sorted list

We compare the first nodes of both lists, add the smaller one to the merged list, move that list's pointer, and repeat until all nodes are merged.

Execution Sample

DSA Go

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next
    }
    if l1 != nil {
        current.Next = l1
    } else {
        current.Next = l2
    }
    return dummy.Next
}

This code merges two sorted linked lists by repeatedly choosing the smaller head node and linking it to the merged list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize dummy and current	dummy->null	current = dummy	dummy->null
2	Compare l1(1) and l2(2)	1->4->5, 2->3->6	current.Next = l1(1), l1 = 4->5	dummy->1->null
3	Move current to 1	4->5, 2->3->6	current = 1	dummy->1->null
4	Compare l1(4) and l2(2)	4->5, 2->3->6	current.Next = l2(2), l2 = 3->6	dummy->1->2->null
5	Move current to 2	4->5, 3->6	current = 2	dummy->1->2->null
6	Compare l1(4) and l2(3)	4->5, 3->6	current.Next = l2(3), l2 = 6	dummy->1->2->3->null
7	Move current to 3	4->5, 6	current = 3	dummy->1->2->3->null
8	Compare l1(4) and l2(6)	4->5, 6	current.Next = l1(4), l1 = 5	dummy->1->2->3->4->null
9	Move current to 4	5, 6	current = 4	dummy->1->2->3->4->null
10	Compare l1(5) and l2(6)	5, 6	current.Next = l1(5), l1 = null	dummy->1->2->3->4->5->null
11	Move current to 5	null, 6	current = 5	dummy->1->2->3->4->5->null
12	l1 is null, attach remaining l2(6)	null, 6	current.Next = l2(6)	dummy->1->2->3->4->5->6->null
13	Return merged list	1->2->3->4->5->6	return dummy.Next	1->2->3->4->5->6->null

💡 l1 becomes null at step 10, remaining l2 nodes attached, merge complete

Variable Tracker

Variable	Start	After 2	After 4	After 6	After 8	After 10	After 12	Final
l1	1->4->5	4->5	4->5	4->5	5	null	null	null
l2	2->3->6	2->3->6	3->6	6	6	6	6	6
current	dummy	1	2	3	4	5	5	5

Key Moments - 3 Insights

Why do we use a dummy node at the start?

The dummy node simplifies linking nodes without checking if merged list is empty. See step 1 and how current starts at dummy.

Why do we move current after linking a node?

Moving current ensures the next node is linked after the last merged node. See steps 3, 5, 7, 9, 11 where current moves forward.

What happens when one list becomes empty?

When l1 is null at step 10, we attach remaining l2 nodes directly (step 12) to finish merging.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of current after step 6?

A Node with value 2

B Node with value 4

C Node with value 3

D Dummy node

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6 in the execution_table.

At which step does l1 become null?

A Step 11

B Step 10

C Step 12

D Step 13

💡 Hint

Look at the 'l1' variable values in variable_tracker after each step.

If l2 started with a smaller first node, how would step 2 change?

A current.Next would point to l2's first node

B current.Next would point to l1's first node

C No change, current.Next stays nil

D Merge would stop immediately

💡 Hint

Step 2 shows which node current.Next points to based on comparison of l1 and l2 heads.

Concept Snapshot

Merge Two Sorted Linked Lists:
- Use a dummy node to start merged list
- Compare heads of both lists
- Link smaller node to merged list
- Move pointer in chosen list and current
- Repeat until one list is empty
- Attach remaining nodes of other list
- Return dummy.Next as merged list head

Full Transcript

To merge two sorted linked lists, we start with a dummy node to simplify linking. We compare the first nodes of both lists and link the smaller one to the merged list. We then move the pointer in that list forward and also move the current pointer in the merged list. We repeat this process until one list becomes empty. At that point, we attach the remaining nodes of the other list to the merged list. Finally, we return the node after the dummy as the head of the merged sorted list. This approach ensures the merged list is sorted and all nodes are included.

Practice

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

easy

A. Remove duplicates from both lists without merging

B. Sort each list separately without combining them

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

D. Reverse both lists and then merge

Solution

1. Step 1: Understand the merge operation

   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 input lists.

3. Final Answer:

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

4. Quick Check:

   Merge = Combine sorted lists [OK]

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

Common Mistakes:

• Thinking merge means sorting each list separately
• Confusing merge with removing duplicates only
• Assuming merge reverses the lists

2. Which of the following is the correct Go syntax to define a node struct for a singly linked list?

easy

A. Node := struct { val int; next Node }

B. struct Node { int val; Node* next; }

C. class Node { int val; Node next; }

D. type Node struct { val int; next *Node }

Solution

1. Step 1: Recall Go struct syntax

   In Go, structs are defined with 'type Name struct { fields }' and pointers use '*'.

2. Step 2: Check each option

   type Node struct { val int; next *Node } uses correct Go syntax with pointer '*Node' for next node.

3. Final Answer:

   type Node struct { val int; next *Node } -> Option D

4. Quick Check:

   Go struct with pointer = type Node struct { val int; next *Node } [OK]

Hint: Go structs use 'type' and pointers with '*' [OK]

Common Mistakes:

• Using C/C++ or Java syntax in Go
• Missing pointer '*' for next node
• Using := inside struct definition

3. What is the output linked list after merging these two sorted lists?

List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null

Assume the merge function returns the head of the merged list.

medium

A. 2 -> 4 -> 6 -> 1 -> 3 -> 5 -> null

B. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

C. 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> null

D. 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

Solution

1. Step 1: Compare first nodes of both lists

   1 (List1) < 2 (List2), so start merged list with 1.

2. Step 2: Continue comparing next nodes in order

   Next compare 3 and 2, 2 is smaller, add 2; then 3 and 4, add 3; then 5 and 4, add 4; then 5 and 6, add 5; finally add 6.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null -> Option B

4. Quick Check:

   Merge sorted lists = sorted combined list [OK]

Hint: Pick smaller node each step to merge sorted lists [OK]

Common Mistakes:

• Appending one list after the other without sorting
• Reversing the order accidentally
• Skipping nodes during merge

4. Given this Go function snippet to merge two sorted linked lists, what is the bug?

func mergeLists(l1, l2 *Node) *Node {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.val < l2.val {
        l1.next = mergeLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeLists(l1, l2.next)
        return l2
    }
}

medium

A. No bug, function correctly merges two sorted lists

B. Missing base case for both lists being nil

C. Incorrect comparison operator, should be <= instead of <

D. Function does not handle cycles in lists

Solution

1. Step 1: Analyze base cases

   Function returns the other list if one is nil, which is correct.

2. Step 2: Check recursive merge logic

   Function compares values and recursively merges the rest correctly.

3. Final Answer:

   No bug, function correctly merges two sorted lists -> Option A

4. Quick Check:

   Recursive merge with base cases = correct [OK]

Hint: Check base cases and recursion for correctness [OK]

Common Mistakes:

• Thinking missing base case for both nil (not needed)
• Confusing < with <= (both work here)
• Ignoring cycle detection (not required here)

5. You have two sorted linked lists:
List1: 1 -> 4 -> 7 -> 10 -> null
List2: 2 -> 3 -> 5 -> 8 -> 12 -> null

Write a Go function to merge these lists iteratively and return the merged list head. What will be the final merged list?

hard

A. 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 10 -> 12 -> null

B. 1 -> 4 -> 7 -> 10 -> 2 -> 3 -> 5 -> 8 -> 12 -> null

C. 2 -> 3 -> 5 -> 8 -> 12 -> 1 -> 4 -> 7 -> 10 -> null

D. 12 -> 10 -> 8 -> 7 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

Solution

1. Step 1: Initialize dummy node and pointer

   Create a dummy node to start merged list and a pointer to track current node.

2. Step 2: Iterate and compare nodes from both lists

   Compare current nodes from List1 and List2, attach smaller to merged list, move pointer forward.

3. Step 3: Attach remaining nodes after one list ends

   Once one list is exhausted, attach the rest of the other list.

4. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 10 -> 12 -> null -> Option A

5. Quick Check:

   Iterative merge keeps sorted order [OK]

Hint: Use dummy node and iterate picking smaller nodes [OK]

Common Mistakes:

• Appending lists without sorting
• Forgetting to attach remaining nodes
• Not using a dummy node causing complex code