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.

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 the order of elements in both lists

C. To find the largest element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merging process

   Merging two sorted linked lists means combining them into one list that keeps the sorted order.

2. Step 2: Identify the goal

   The goal is to have a new linked list that contains all elements from both lists in sorted order.

3. Final Answer:

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

4. Quick Check:

   Merging = combine sorted lists [OK]

Hint: Merging keeps order and combines all elements [OK]

Common Mistakes:

• Thinking merging reverses lists
• Only finding largest element
• Removing duplicates instead of merging

2. Which of the following is the correct way to start merging two sorted linked lists in Python?

easy

A. def mergeLists(l1, l2):
current = ListNode(0)
dummy = current.next

B. def mergeLists(l1, l2):
dummy = null
current = dummy

C. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy

D. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy.next

Solution

1. Step 1: Initialize dummy and current nodes properly

   We create a dummy node with value 0 and set current to dummy to build the merged list.

2. Step 2: Check options for correct syntax

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy correctly creates dummy and current pointing to dummy. def mergeLists(l1, l2): dummy = ListNode(0) current = dummy.next incorrectly sets current = dummy.next which is initially None.

3. Final Answer:

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy -> Option C

4. Quick Check:

   Dummy node with value 0 starts merge [OK]

Hint: Start with dummy node value 0 and current pointing to dummy [OK]

Common Mistakes:

• Setting current to dummy.next
• Swapping dummy and current incorrectly
• Setting dummy to null

3. What will be the output linked list after merging these two sorted lists? List 1: 1 -> 3 -> 5 -> null List 2: 2 -> 4 -> 6 -> null Use the merge logic to combine them.

medium

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

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

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

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

Solution

1. Step 1: Compare nodes from both lists in order

   Start with 1 (List 1) and 2 (List 2). 1 is smaller, add 1. Then compare 3 and 2, add 2. Continue comparing and adding smaller nodes.

2. Step 2: Build merged list step-by-step

   Merged list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null after adding all nodes in sorted order.

3. Final Answer:

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

4. Quick Check:

   Sorted merge combines nodes in ascending order [OK]

Hint: Pick smaller node each step to keep order [OK]

Common Mistakes:

• Appending one list fully before the other
• Mixing node order incorrectly
• Skipping nodes during merge

4. Identify the error in this merge function snippet:

def mergeLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
    current.next = l1 if l1 else l2
    return dummy.next

medium

A. The 'current' pointer is not moved forward inside the loop

B. The dummy node is not initialized correctly

C. The function does not handle empty input lists

D. The return statement should return 'current' instead of 'dummy.next'

Solution

1. Step 1: Check pointer updates inside the loop

   After assigning current.next, the current pointer must move forward to current.next to continue building the list.

2. Step 2: Identify missing current update

   The code misses 'current = current.next' inside the while loop, causing an infinite loop or incorrect list.

3. Final Answer:

   The 'current' pointer is not moved forward inside the loop -> Option A

4. Quick Check:

   Move current forward after linking nodes [OK]

Hint: Always move current pointer after linking a node [OK]

Common Mistakes:

• Forgetting to move current pointer
• Returning wrong node
• Not handling empty lists (though not error here)

5. Given two sorted linked lists where one list is empty and the other is 0 -> 2 -> 4 -> null, what should the merged list be?

medium

A. 0 -> null

B. null

C. 4 -> 2 -> 0 -> null

D. 0 -> 2 -> 4 -> null

Solution

1. Step 1: Understand merging with an empty list

   If one list is empty, the merged list is just the non-empty list as it is already sorted.

2. Step 2: Apply to given lists

   Since the second list is empty and the first is 0 -> 2 -> 4 -> null, the merged list remains 0 -> 2 -> 4 -> null.

3. Final Answer:

   0 -> 2 -> 4 -> null -> Option D

4. Quick Check:

   Merging with empty list returns the other list [OK]

Hint: Empty list merge returns the other list unchanged [OK]

Common Mistakes:

• Returning null when one list is empty
• Reversing the non-empty list
• Returning only the first node