Merge Two Sorted Linked Lists in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new node with the given value.

DSA C++

ListNode* newNode = new ListNode([1]);

Drag options to blanks, or click blank then click option'

Anode

Bval

Chead

Dnullptr

Attempts:

3 left

💡 Hint

Common Mistakes

Using a pointer instead of a value

Passing nullptr instead of a value

The constructor of ListNode takes the value to store in the node. We pass val to create a node with that value.

2fill in blank

medium

Complete the code to move the pointer to the next node in the list.

DSA C++

current = current->[1];

Drag options to blanks, or click blank then click option'

Anext

Bprev

Cchild

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using prev which is for doubly linked lists

Using unrelated pointer names

In a singly linked list, each node points to the next node using the next pointer.

3fill in blank

hard

Fix the error in the condition to check if the first list is empty.

DSA C++

if (list1 == [1]) return list2;

Drag options to blanks, or click blank then click option'

Anullptr

BNULL

C0

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or NULL which are older styles

Using false which is a boolean, not a pointer

In modern C++, nullptr is the preferred way to check for a null pointer instead of NULL or 0.

4fill in blank

hard

Fill both blanks to correctly compare node values and assign the next pointer.

DSA C++

if (list1->val [1] list2->val) {
    merged->next = list1;
    list1 = list1->[2];
} else {
    merged->next = list2;
    list2 = list2->next;
}

Drag options to blanks, or click blank then click option'

A<

Bnext

C>

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of <

Using prev instead of next to move forward

We compare if list1->val is less than list2->val. If yes, we link merged->next to list1 and move list1 forward using next.

5fill in blank

hard

Fill all three blanks to complete the merge function that returns the merged list.

DSA C++

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (list1 == [1]) return list2;
    if (list2 == [2]) return list1;
    if (list1->val < list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return [3];
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

Drag options to blanks, or click blank then click option'

ANULL

Bnullptr

Clist1

Dlist2

Attempts:

3 left

💡 Hint

Common Mistakes

Using NULL instead of nullptr

Returning the wrong list pointer

We check if either list is empty using nullptr. Then we recursively merge and return the smaller node. When list1->val is smaller, we return list1 after linking its next.

Practice

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

easy

A. Sort each list separately before merging

B. Reverse the order of nodes in both lists

C. Combine nodes from both lists maintaining sorted order

D. Remove duplicate nodes from both lists

Solution

1. Step 1: Understand the merge operation

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

2. Step 2: Maintain sorted order during merge

   We pick the smaller node from the heads of both lists repeatedly to keep the merged list sorted.

3. Final Answer:

   Combine nodes from both lists maintaining sorted order -> Option C

4. Quick Check:

   Merge = Combine sorted lists [OK]

Hint: Always pick the smaller node first to keep order [OK]

Common Mistakes:

• Trying to reverse lists instead of merging
• Sorting lists again after merging
• Ignoring order and just concatenating

2. Which of the following is the correct way to declare a node structure for a singly linked list in C++?

easy

A. struct Node { int data; Node next; };

B. class Node { int data; Node next; };

C. class Node { int data; Node* next; };

D. struct Node { int data; Node* next; };

Solution

1. Step 1: Understand node structure in C++

   A node should have data and a pointer to the next node.

2. Step 2: Check pointer usage

   Using Node* next is correct to point to the next node; Node next would cause infinite size error.

3. Final Answer:

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

4. Quick Check:

   Node pointer = Node* next [OK]

Hint: Use pointers for next node in linked list [OK]

Common Mistakes:

• Using object instead of pointer for next node
• Missing semicolon after struct
• Using class without access specifier

3. What will be the output linked list after merging these two sorted lists?
List1: 1 -> 3 -> 5 -> null
List2: 2 -> 4 -> 6 -> null
Using a standard merge algorithm?

medium

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

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

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

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

Solution

1. Step 1: Compare heads of both lists

   Start with 1 (List1) and 2 (List2). 1 is smaller, so first node is 1.

2. Step 2: Continue picking smaller nodes

   Next compare 3 and 2, pick 2; then 3 and 4, pick 3; then 5 and 4, pick 4; then 5 and 6, pick 5; finally 6.

3. Final Answer:

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

4. Quick Check:

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

Hint: Pick smaller head node repeatedly [OK]

Common Mistakes:

• Appending one list after the other without sorting
• Mixing node order incorrectly
• Skipping nodes during merge

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

Node* merge(Node* l1, Node* l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1->data < l2->data) {
    l1->next = merge(l1->next, l2);
    return l1;
  } else {
    l2->next = merge(l1, l2->next);
    return l2;
  }
}

medium

A. No error, code correctly merges two sorted lists

B. Missing base case for empty lists

C. Incorrect comparison operator used

D. Function does not handle cyclic lists

Solution

1. Step 1: Check base cases

   Code returns the other list if one is empty, which is correct.

2. Step 2: Check recursive merge logic

   It compares data correctly and recursively merges the rest, returning the smaller node.

3. Final Answer:

   No error, code correctly merges two sorted lists -> Option A

4. Quick Check:

   Recursive merge logic correct [OK]

Hint: Check base cases and recursion carefully [OK]

Common Mistakes:

• Forgetting to return merged list
• Wrong base case conditions
• Using wrong pointers in recursion

5. You have two sorted linked lists:
List1: 1 -> 4 -> 5 -> 7 -> null
List2: 2 -> 3 -> 6 -> 8 -> 9 -> null
Write the merged list after merging them. Then, if you want to remove duplicates from the merged list, what will be the final list?
Assume duplicates can appear after merge.

hard

A. Merged: 1 -> 4 -> 5 -> 7 -> 2 -> 3 -> 6 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

B. Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

C. Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> null

D. Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 4 -> 5 -> 7 -> 2 -> 3 -> 6 -> 8 -> 9 -> null

Solution

1. Step 1: Merge both sorted lists

   Pick nodes in order: 1,2,3,4,5,6,7,8,9 forming a sorted merged list.

2. Step 2: Remove duplicates if any

   Since all values are unique, the list remains the same after removing duplicates.

3. Final Answer:

   Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null; After removing duplicates: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null -> Option B

4. Quick Check:

   Sorted merge with unique values [OK]

Hint: Merge sorted, then remove duplicates if any [OK]

Common Mistakes:

• Concatenating lists without sorting
• Assuming duplicates always exist
• Removing nodes incorrectly