Merge Two Sorted Linked Lists in DSA Go - 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 ID numbers. You want to combine these two sorted lists into one sorted list so that you can show all contacts in order.

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

📋 What You'll Learn

Create two sorted linked lists using the provided ListNode struct

Create a helper variable to start the merged list

Write the core logic to merge the two sorted linked lists

Print the merged linked list in the format: 1 -> 2 -> 3 -> null

💡 Why This Matters

🌍 Real World

Merging sorted lists is common in apps that combine data from multiple sources, like contact lists or event schedules.

💼 Career

Understanding linked list merging is important for software engineers working with data structures, algorithms, and optimizing data processing.

1

Create Two Sorted Linked Lists

Create two sorted linked lists using the ListNode struct. The first list should have nodes with values 1, 3, and 5. The second list should have nodes with values 2, 4, and 6. Use variables list1 and list2 for the heads of these lists.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    // Create list1 with nodes 1 -> 3 -> 5 -> null
    // Create list2 with nodes 2 -> 4 -> 6 -> null
    // Your code here
}

Hint

Use the &ListNode{Val: value, Next: nextNode} syntax to create linked list nodes.

2

Create a Dummy Node to Start the Merged List

Create a variable called dummy as a new ListNode with value 0. Also create a variable called current that points to dummy. These will help build the merged list.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    list1 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 5, Next: nil}}}
    list2 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 6, Next: nil}}}

    // Create dummy node and current pointer
    // Your code here
}

Hint

Use dummy := &ListNode{Val: 0} and current := dummy.

3

Merge the Two Sorted Lists

Write a for loop that continues while both list1 and list2 are not nil. Inside the loop, compare list1.Val and list2.Val. Attach the smaller node to current.Next, then move current and the chosen list forward by one node. After the loop, attach the remaining nodes from list1 or list2 to current.Next.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    list1 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 5, Next: nil}}}
    list2 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 6, Next: nil}}}

    dummy := &ListNode{Val: 0}
    current := dummy

    // Merge list1 and list2
    // Your code here
}

Hint

Use a for loop with condition list1 != nil && list2 != nil. Inside, compare list1.Val and list2.Val to attach the smaller node.

4

Print the Merged Linked List

Write a for loop to print the merged linked list starting from dummy.Next. Print each node's value followed by " -> ". After the loop, print "null" to show the end of the list.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    list1 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 5, Next: nil}}}
    list2 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 6, Next: nil}}}

    dummy := &ListNode{Val: 0}
    current := dummy

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            current.Next = list1
            list1 = list1.Next
        } else {
            current.Next = list2
            list2 = list2.Next
        }
        current = current.Next
    }

    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }

    // Print the merged list
    // Your code here
}

Hint

Use a for loop starting at dummy.Next to print each node's value followed by " -> ". After the loop, print "null".

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