Merging Missions - codepath/compsci_guides GitHub Wiki

TIP102 Unit 7 Session 1 Standard (Click for link to problem statements)

Problem 8: Merging Missions

The Avengers are planning multiple missions, and each mission has a priority level represented as a node in a linked list. You are given the heads of two sorted linked lists, mission1 and mission2, where each node represents a mission with its priority level.

Implement a recursive function merge_missions() which merges these two mission lists into one sorted list, ensuring that the combined list maintains the correct order of priorities. The merged list should be made by splicing together the nodes from the first two lists.

Return the head of the merged mission linked list.

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Recursion, Linked Lists

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What is the main task in this problem?
    • A: The task is to merge two sorted linked lists into one sorted linked list using a recursive approach.
  • Q: Are the linked lists always sorted?
    • A: Yes, the problem specifies that the linked lists are sorted.
HAPPY CASE
Input: mission1 = Node(1, Node(2, Node(4))), mission2 = Node(1, Node(3, Node(4)))
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Explanation: The merged linked list correctly combines the missions while maintaining sorted order.

EDGE CASE
Input: mission1 = None, mission2 = Node(1, Node(2, Node(3)))
Output: 1 -> 2 -> 3
Explanation: If one of the lists is empty, the merged list should just be the other list.

Input: mission1 = Node(5), mission2 = Node(1, Node(3, Node(7)))
Output: 1 -> 3 -> 5 -> 7
Explanation: Handles cases where the lists do not overlap in values.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Merging Sorted Lists, we want to consider the following approaches:

  • Recursive Merging: Compare the heads of the two lists and recursively build the merged list by attaching the smaller node to the merged list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • Use recursion to compare the nodes at the head of each list, attach the smaller node to the merged list, and recurse on the remaining nodes.

Recursive Approach:

1) Base case: If one list is empty, return the other list.
2) Compare the values of the heads of the two lists.
   a) If the value of `mission1` is smaller, attach it to the merged list and recurse on the next node of `mission1` and the head of `mission2`.
   b) If the value of `mission2` is smaller or equal, attach it to the merged list and recurse on the head of `mission1` and the next node of `mission2`.
3) Return the head of the merged list.

⚠️ Common Mistakes

  • Failing to handle the base case where one of the lists is empty, which would lead to incorrect results.
  • Incorrectly attaching nodes leading to a loss of the linked list structure.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def merge_missions(mission1, mission2):
    if not mission1:
        return mission2
    if not mission2:
        return mission1

    if mission1.value < mission2.value:
        mission1.next = merge_missions(mission1.next, mission2)
        return mission1
    else:
        mission2.next = merge_missions(mission1, mission2.next)
        return mission2

# For testing
def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> " if current.next else "\n")
        current = current.next

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through the merge_missions function with the inputs mission1 = Node(1, Node(2, Node(4))) and mission2 = Node(1, Node(3, Node(4))). The function should return 1 -> 1 -> 2 -> 3 -> 4 -> 4.
  • Test the function with edge cases such as one list being empty or both lists having the same elements.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(N + M) where N and M are the lengths of the two linked lists. The function processes each node once, leading to linear time complexity.
  • Space Complexity: O(N + M) due to the recursion stack. The depth of recursion is proportional to the total number of nodes in both lists.