Super Sandwich II - codepath/compsci_guides GitHub Wiki

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

Problem 5: Super Sandwich II

Below is an iterative solution to the merge_orders() function from the previous problem. Compare your recursive solution to the iterative solution below.

Iterative Solution

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

def merge_orders(sandwich_a, sandwich_b):
    # If either list is empty, return the other
    if not sandwich_a:
        return sandwich_b
    if not sandwich_b:
        return sandwich_a

    # Start with the first node of sandwich_a
    head = sandwich_a
    
    # Loop through both lists until one is exhausted
    while sandwich_a and sandwich_b:
        # Store the next pointers
        next_a = sandwich_a.next
        next_b = sandwich_b.next
        
        # Merge sandwich_b after sandwich_a
        sandwich_a.next = sandwich_b
        
        # If there's more in sandwich_a, add it after sandwich_b
        if sandwich_a:
            sandwich_b.next = next_a
        
        # Move to the next nodes
        sandwich_a = next_a
        sandwich_b = next_b

    # Return the head of the new merged list
    return head

Recursive Solution

def merge_orders(sandwich_a, sandwich_b):
    # Base case: if one of the lists is empty, return the other
    if not sandwich_a:
        return sandwich_b
    if not sandwich_b:
        return sandwich_a
    
    # Recursive case: merge first nodes of both lists and recurse
    next_a = sandwich_a.next
    next_b = sandwich_b.next
    
    sandwich_a.next = sandwich_b
    sandwich_b.next = merge_orders(next_a, next_b)
    
    return sandwich_a

Comparison

Similarities:

1. Purpose: Both the iterative and recursive solutions aim to merge two linked lists by alternating nodes from each list.
2. Functionality: Both solutions ensure that the nodes from sandwich_a and sandwich_b are merged into a single linked list in an alternating pattern.

Differences:

1. Approach:

   • The iterative solution uses a loop to traverse both linked lists, weaving nodes together in each iteration.
   • The recursive solution achieves the same result by using recursive function calls to process the nodes one pair at a time.

2. Complexity:

   • Space Complexity:
     • The iterative approach has a space complexity of O(1) because it uses a constant amount of extra space beyond the input lists.
     • The recursive approach has a space complexity of O(N + M) due to the recursion stack, where N and M are the lengths of the two linked lists.
   • Time Complexity: Both solutions have a time complexity of O(N + M) because they process each node exactly once.

3. Performance:

   • The iterative approach is generally more efficient in terms of memory usage, as it does not involve the overhead of recursive calls. It is also less prone to stack overflow errors, especially when dealing with large lists.
   • The recursive approach is often considered more elegant and easier to understand, especially for those familiar with recursive patterns, but it may be less practical for very large lists.

Preference Discussion:

• Personal Preference: The choice between iterative and recursive solutions depends on the context. For larger inputs where stack depth might be a concern, the iterative solution is more efficient and practical. However, for smaller or moderate-sized inputs, the recursive approach can be more intuitive and easier to write.
• Pod Discussion: When discussing with your podmates, consider the trade-offs between readability, maintainability, and performance. The recursive approach is more concise and aligns with the recursive nature of linked lists, while the iterative approach offers better performance and avoids potential issues with recursion limits.