Merge Two Sorted Linked Lists — Leetcode

Problem

Examples

• Example 01

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

• Example 02

Input: list1 = [], list2 = []
Output: []

• Example 03

Input: list1 = [], list2 = [0]
Output: [0]

Algorithm Walk-through

Initial

current = dummy = Node()

After executing the source code, the state of the linked lists shown in the following:

Iteration 01

if ll1.val >= ll2.val:
    current.next = ll2
    ll2 = ll2.next
current = current.next

After executing the source code, the state of the linked lists shown in the following:

Iteration 02

if ll1.val < ll2.val:
    current.next = ll1
    ll1 = ll1.next
current = current.next

After executing the source code, the state of the linked lists shown in the following:

Iteration 03

if ll1.val >= ll2.val:
    current.next = ll2
    ll2 = ll2.next
current = current.next

After executing the source code, the state of the linked lists shown in the following:

Iteration 04

if ll1.val >= ll2.val:
    current.next = ll2
    ll2 = ll2.next
current = current.next

After executing the source code, the state of the linked lists shown in the following:

Iteration 05

if ll1.val >= ll2.val:
    current.next = ll2
    ll2 = ll2.next
current = current.next

After executing the source code, the state of the linked lists shown in the following:

Finished iterations, Finish off last part of linked list and Return

if ll1 or ll2:
    current.next = ll1 if ll1 else ll2
            
return dummy.next

After executing the source code, the state of the linked lists shown in the following:

Solution

class Node:
  def __init__(self, val = 0, next=None): 
    self.val = val
    self.next = next
      
def MergeTwoLists(ll1, ll2):
    current = dummy = Node()
    while ll1 and ll2:
        if ll1.val < ll2.val:
            current.next = ll1
            ll1 = ll1.next
        else:
            current.next = ll2
            ll2 = ll2.next
        current = current.next
    
    if ll1 or ll2:
        current.next = ll1 if ll1 else ll2
            
    return dummy.next
LL1 = Node(1, Node(2, Node(4)))
LL2 = Node(1, Node(3, Node(4)))
ll3 = MergeTwoLists(LL1, LL2)

Time and Space Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

Takeaways

Thank you for reading this short problem solving question. If anyone knows a better or faster time complexity to solve this question, feel free to comment and feedback. Peace! ✌️