Merge Two Sorted Linked Lists in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging two sorted linked lists

What is the printed state of the merged linked list after merging these two sorted lists?

List 1: 1 -> 3 -> 5 -> null
List 2: 2 -> 4 -> 6 -> null

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode 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;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.print("null");
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        ListNode merged = mergeTwoLists(l1, l2);
        printList(merged);
    }
}

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

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

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

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

💡 Hint

Compare the values of nodes from both lists one by one and link the smaller one first.

The merge function compares nodes from both lists and appends the smaller node to the merged list. This results in a sorted merged list combining all nodes.

❓ Predict Output

intermediate

Output when one list is empty

What is the printed state of the merged linked list after merging these two lists?

List 1: null
List 2: 0 -> 7 -> 8 -> null

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode 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;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.print("null");
    }

    public static void main(String[] args) {
        ListNode l1 = null;

        ListNode l2 = new ListNode(0);
        l2.next = new ListNode(7);
        l2.next.next = new ListNode(8);

        ListNode merged = mergeTwoLists(l1, l2);
        printList(merged);
    }
}

A 0 -> 7 -> 8 -> null

B null

C 0 -> null

D 7 -> 8 -> null

💡 Hint

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

Since the first list is empty, the merged list is just the second list unchanged.

🔧 Debug

advanced

Identify the bug in the merge function

What error will this code produce when merging two sorted linked lists?

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode 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;
        }
        // Bug: forgot to attach remaining nodes
        return dummy.next;
    }
}

A The merged list will be incomplete, missing nodes after the first while loop

B NullPointerException when accessing l1.val or l2.val

C StackOverflowError due to infinite recursion

D SyntaxError due to missing semicolon

💡 Hint

Check what happens after the while loop ends.

The code does not attach the remaining nodes from either list after the while loop, so the merged list is incomplete.

❓ Predict Output

advanced

Output of merging lists with duplicate values

What is the printed state of the merged linked list after merging these two sorted lists?

List 1: 1 -> 3 -> 5 -> null
List 2: 1 -> 2 -> 5 -> null

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode 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;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.print("null");
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(5);

        ListNode merged = mergeTwoLists(l1, l2);
        printList(merged);
    }
}

A 1 -> 1 -> 3 -> 2 -> 5 -> 5 -> null

B 1 -> 1 -> 2 -> 3 -> 5 -> 5 -> null

C 1 -> 3 -> 5 -> 1 -> 2 -> 5 -> null

D 1 -> 2 -> 3 -> 5 -> null

💡 Hint

Duplicates are allowed and should appear in order.

The merge function includes duplicates by comparing with <= and appending nodes accordingly.

❓ Predict Output

expert

Output after merging lists with negative and positive values

What is the printed state of the merged linked list after merging these two sorted lists?

List 1: -3 -> 0 -> 4 -> null
List 2: -2 -> 1 -> 3 -> null

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode 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;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.print("null");
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(-3);
        l1.next = new ListNode(0);
        l1.next.next = new ListNode(4);

        ListNode l2 = new ListNode(-2);
        l2.next = new ListNode(1);
        l2.next.next = new ListNode(3);

        ListNode merged = mergeTwoLists(l1, l2);
        printList(merged);
    }
}

A -2 -> -3 -> 0 -> 1 -> 3 -> 4 -> null

B -3 -> 0 -> 4 -> -2 -> 1 -> 3 -> null

C -3 -> -2 -> 0 -> 1 -> 3 -> 4 -> null

D -3 -> -2 -> 1 -> 0 -> 3 -> 4 -> null

💡 Hint

Negative values are merged in sorted order just like positive values.

The merge function compares values and merges nodes in ascending order regardless of sign.

Practice

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

easy

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

B. To reverse both linked lists

C. To find the maximum element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the input lists

   Two linked lists are sorted individually, meaning their elements are in ascending order.

2. Step 2: Merge while maintaining order

   The goal is to combine these two lists into one sorted list that contains all elements from both.

3. Final Answer:

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

4. Quick Check:

   Merging sorted lists means combining all elements in order [OK]

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

Common Mistakes:

• Thinking merge means reversing lists
• Assuming merge removes duplicates
• Confusing merge with finding max element

2. Which of the following Java method signatures correctly represents a function to merge two sorted linked lists of integers?

easy

A. public int merge(ListNode l1, ListNode l2)

B. public void merge(int l1, int l2)

C. public ListNode merge(ListNode l1, ListNode l2)

D. public ListNode merge(int[] l1, int[] l2)

Solution

1. Step 1: Identify correct parameter types

   The function should accept two linked lists, so parameters must be ListNode types, not primitives or arrays.

2. Step 2: Identify correct return type

   The function returns a merged linked list, so return type should be ListNode, not void or int.

3. Final Answer:

   public ListNode merge(ListNode l1, ListNode l2) -> Option C

4. Quick Check:

   Method with ListNode params and return type is correct [OK]

Hint: Method merges two ListNode inputs and returns ListNode [OK]

Common Mistakes:

• Using primitive types instead of ListNode
• Returning void instead of ListNode
• Using arrays instead of linked lists

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

List 1: 1 -> 3 -> 5 -> null
List 2: 2 -> 4 -> 6 -> null

medium

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

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

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

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

Solution

1. Step 1: Compare first nodes of both lists

   1 (List 1) is less than 2 (List 2), so 1 is first in merged list.

2. Step 2: Continue comparing next nodes

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

3. Final Answer:

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

4. Quick Check:

   Merge keeps ascending order combining both lists [OK]

Hint: Pick smaller head node repeatedly to merge sorted lists [OK]

Common Mistakes:

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

4. Given the following code snippet to merge two sorted linked lists, what is the error?

public ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    } else {
        l2.next = merge(l1, l2.next);
        return l2;
    }
}

medium

A. Missing base case for both lists being null

B. No error; code correctly merges two sorted linked lists

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

D. Function does not handle empty lists properly

Solution

1. Step 1: Check base cases

   Code returns the other list if one is null, correctly handling empty lists.

2. Step 2: Check recursive merge logic

   Compares values, recursively merges next nodes, and returns the smaller node, which is correct.

3. Final Answer:

   No error; code correctly merges two sorted linked lists -> Option B

4. Quick Check:

   Recursive merge with base cases is correct [OK]

Hint: Check base cases and recursive calls carefully [OK]

Common Mistakes:

• Forgetting to return merged list
• Incorrect base case handling
• Wrong comparison operator causing order issues

5. You have two sorted linked lists:

List 1: 1 -> 4 -> 5 -> null
List 2: 1 -> 3 -> 4 -> null

After merging, what is the correct merged list?
Also, explain why the merged list contains duplicate values.

hard

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

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

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

D. 1 -> 1 -> 4 -> 5 -> null

Solution

1. Step 1: Merge nodes in ascending order

   Compare heads: both 1, add both 1s. Then 4 vs 3, add 3. Then 4 vs 4, add both 4s. Finally add 5.

2. Step 2: Understand duplicates in merged list

   Duplicates appear because both lists contain the same values independently; merge keeps all elements without removing duplicates.

3. Final Answer:

   1 -> 1 -> 3 -> 4 -> 4 -> 5 -> null -> Option A

4. Quick Check:

   Merge keeps all elements including duplicates [OK]

Hint: Merge keeps duplicates if present in input lists [OK]

Common Mistakes:

• Removing duplicates during merge
• Appending lists without sorting
• Skipping nodes with same values