Merge Two Sorted (Linked) Lists

Merge Two Sorted (Linked) Lists#

https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/

Explain problem first, I got confused at first.

Assumptions#

Each given input will have exactly one solution
Same element cannot be used twice
Order of indices does not matter

Test Cases#

Intuition#

Code Walkthrough#

from typing import *

class Node:
    curr_node_value: Any
    # next_node: Node
    def __init__(self, curr_node_value: Any = None):
        # a node can hold a current value and by default its next node is None
        # however we can assign values to the next of a node, but the next must be of object node as denoted
        # note the distinction between curr node value and next node, they are diff
        self.curr_node_value = curr_node_value
        self.next_node = None

class LinkedList:
    def __init__(self):
        # key point is that end of every llist, it points to None always
        self.head = None
        
    @staticmethod
    def traverse(head_node: Node):
        # stay true to the idea of having None as the "last last Node"
        temp = head_node
        
        while temp is not None:
            print(temp.curr_node_value)
            temp = temp.next_node
            if temp is None:
                print("None")
                

ll1_first = Node(1)
ll1_second = Node(2)
ll1_third = Node(3)

ll2_first = Node(4)
ll2_second = Node(5)
ll2_third = Node(6)

# create llist 1
ll1 = LinkedList()
ll1.head = ll1_first
ll1.head.next_node = ll1_second
ll1.head.next_node.next_node = ll1_third

# create llist 2
ll2 = LinkedList()
ll2.head = ll2_first
ll2.head.next_node = ll2_second
ll2.head.next_node.next_node = ll2_third

merged_sorted_llist = LinkedList()
merged_sorted_llist.head = Node(-100)

prehead_node = Node(-100)
temp_node = prehead_node


ll1_head = ll1.head
ll2_head = ll2.head

while ll1_head is not None and ll2_head is not None:
    
    # start with list 1
    
    if ll1_head.curr_node_value <= ll2_head.curr_node_value:
        temp_node.next_node = ll1_head
        ll1_head = ll1_head.next_node
    
    else:
        temp_node.next_node = ll2_head
        ll2_head = ll2_head.next_node
    
    temp_node = temp_node.next_node
        
temp_node.next_node = ll1_head or ll2_head
        

merged_sorted_llist.traverse(prehead_node.next_node)

1
2
3
4
5
6
None

https://leetcode.com/problems/merge-two-sorted-lists/discuss/759870/Python3-Solution-with-a-Detailed-Explanation-dummy-explained

Time Complexity#

Time complexity: \(\O(n)\). We traverse the list containing \(n\) elements only once. Each lookup in the table costs only \(\O(1)\) time.

Loosely speaking, this means in each for loop from line 22 to 26, each line takes \(\O(1)\) time, so in a typical single iteration, we use around \(\O(3)\) time, and looping it \(n\) times takes

\[ n \cdot \O(3) \approx \O(3n) \approx \O(n) \]

Space Complexity#

Space complexity: \(\O(n)\). The extra space required depends on the number of items stored in the dictionary seen, which stores at most \(n\) elements.