Merge Two Sorted Linked Lists in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

To create a new sorted linked list that contains all elements from both lists in order.

beginner

In merging two sorted linked lists, why do we compare the current nodes of both lists?

To decide which node has the smaller value and should be added next to the merged list, keeping the order sorted.

intermediate

What happens when one linked list is fully traversed before the other during merging?

The remaining nodes of the other list are directly attached to the merged list since they are already sorted.

intermediate

Show the step-by-step merge result of these two sorted lists:<br>List1: 1 -> 3 -> 5<br>List2: 2 -> 4 -> 6

Step 1: Compare 1 and 2, add 1<br>Step 2: Compare 3 and 2, add 2<br>Step 3: Compare 3 and 4, add 3<br>Step 4: Compare 5 and 4, add 4<br>Step 5: Compare 5 and 6, add 5<br>Step 6: Add remaining 6<br>Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6

intermediate

What is the time complexity of merging two sorted linked lists of lengths m and n?

O(m + n) because each node from both lists is visited exactly once during the merge.

What should you do when the current node of List1 has a smaller value than List2 during merging?

A Add List2's node to the merged list and move List2's pointer forward

B Restart the merge

C Skip both nodes

D Add List1's node to the merged list and move List1's pointer forward

We add the smaller node to keep the merged list sorted and move that list's pointer forward.

If one list is empty, what is the merged list?

A Empty list

B The non-empty list as is

C A new empty list

D A reversed list

If one list is empty, the merged list is just the other list since it is already sorted.

Which data structure is best suited for merging two sorted linked lists?

A Linked List

B Queue

C Stack

D Array

Linked lists are used because the problem is about merging two sorted linked lists.

What is the first step in merging two sorted linked lists?

A Create a dummy node to start the merged list

B Reverse both lists

C Sort both lists again

D Delete duplicates

A dummy node helps simplify adding nodes to the merged list without special cases.

What happens if you forget to attach the remaining nodes after one list ends?

A Merged list will have duplicates

B Merged list will be sorted

C Merged list will be incomplete

D No effect

The merged list will miss the remaining nodes, so it will be incomplete.

Explain how to merge two sorted linked lists step-by-step.

Think about walking through both lists together.

Describe the role of a dummy node in merging two sorted linked lists.

Dummy node is like a placeholder before the real list.