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

Recall & Review

beginner

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

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

beginner

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

We compare to decide which node has the smaller value so it can be added next to the merged list, keeping the merged list sorted.

intermediate

What happens when one linked list is fully traversed but the other still has nodes left during merging?

All remaining nodes from the non-empty list are appended to the merged list because they are already sorted.

intermediate

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

A dummy node acts as a starting point for the merged list, simplifying the code by avoiding special cases for the head node.

intermediate

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

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

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

A Compare the first nodes of both lists

B Reverse both lists

C Create a new empty list and add all nodes from the first list

D Delete duplicates from both lists

We start by comparing the first nodes to decide which node to add first to the merged list.

If the first list's current node value is smaller, what do we do?

A Add the node from the first list to the merged list

B Add the node from the second list

C Skip the node from the first list

D Stop merging

We add the smaller node to keep the merged list sorted.

What do we do after adding a node from one list to the merged list?

A Move to the next node in the other list

B Move to the next node in that list

C Restart from the head of both lists

D Delete the added node

We move forward in the list from which we took the node to continue merging.

When is the merging process complete?

A When the second list is empty

B When the first list is empty

C When both lists are fully traversed

D After adding the first node

Merging finishes only after all nodes from both lists are added.

Why is a dummy node useful in merging linked lists?

A It stores the largest value

B It reverses the lists

C It deletes duplicate nodes

D It helps avoid special cases for the head of the merged list

The dummy node simplifies code by providing a fixed starting point.

Describe step-by-step how to merge two sorted linked lists into one sorted linked list.

Think about how you pick the smallest item from two sorted lines of people.

Explain why the time complexity of merging two sorted linked lists is O(m + n).

Consider how many total steps you take to look at every item in both lists.