Advertisement
kai-rocket

Merge Two Sorted Lists

Oct 12th, 2021
671
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.24 KB | None
  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  8.         # Handle edge cases where either or both lists are None
  9.         if not l1:
  10.             return l2
  11.         if not l2:
  12.             return l1
  13.        
  14.         result_head = None
  15.         result_tail = None
  16.        
  17.         # Keep track of pointers #1 and #2
  18.         p1 = l1
  19.         p2 = l2
  20.        
  21.         # While neither pointer #1 and #2 have reached end of their respective LLs:
  22.         while p1 and p2:
  23.        
  24.             # If p1 <= p2:
  25.             if p1.val <= p2.val:
  26.                
  27.                 # Keep track of p1's original next node
  28.                 l1_next_node = p1.next
  29.                 # Reset p1.next to avoid circular pointers
  30.                 p1.next = None
  31.                
  32.                 # Add p1 to result
  33.                 # If this is the 1st node in the result, set result head
  34.                 if not result_head:
  35.                     result_head = p1
  36.                 # If this is NOT the 1st node in the result, add p1 to end of result
  37.                 else:
  38.                     result_tail.next = p1
  39.                 # Increment result_tail
  40.                 result_tail = p1
  41.                    
  42.                 # Increment p1
  43.                 p1 = l1_next_node
  44.                
  45.             # Else (if p2 > p1)
  46.             else:
  47.                 # Add p2 to result
  48.                 l2_next_node = p2.next
  49.                 p2.next = None
  50.                
  51.                 if not result_head:
  52.                     result_head = p2
  53.                 else:
  54.                     result_tail.next = p2
  55.                 # Increment result_tail
  56.                 result_tail = p2
  57.                
  58.                 # Increment p2
  59.                 p2 = l2_next_node
  60.                
  61.         # If p1 is None:
  62.         if not p1:
  63.             # Add rest of p2's list to result
  64.             result_tail.next = p2
  65.         # Else
  66.         else:
  67.             # Add rest of p1's list to result
  68.             result_tail.next = p1
  69.            
  70.         # Return result_head
  71.         return result_head
Advertisement
RAW Paste Data Copied
Advertisement