21. Merge Two Sorted Lists

Easy

Problem:

Merge two sorted linked lists.

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

https://leetcode.com/problems/merge-two-sorted-lists/

What to learn:

Precedence of Python Operators

Operators	Meaning
()	Parentheses
**	Exponent
+x, -x, ~x	Unary plus, Unary minus, Bitwise NOT
*, /, //, %	Multiplication, Division, Floor division, Modulus
+, -	Addition, Subtraction
<<, >>	Bitwise shift operators
&	Bitwise AND
^	Bitwise XOR
|	Bitwise OR
==, !=, >, >=, <, <=, is, is not, in, not in	Comparisons, Identity, Membership operators
not	Logical NOT
and	Logical AND
or	Logical OR
lambda	Lambda function

Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        node = ListNode()
        head = node

        while list1 and list2 :
            if list1.val <= list2.val:
                
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next
            
        if list1:
            head.next = list1

        if list2:
            head.next = list2
        
        return 

Recursive

First, compare the values of list1 and list2, and make the smaller value come to the left. Then, call recursively so that 'next' links to the following value.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if (not list1) or (list2  list1.val > list2.val):
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1

Swap two variables

When swapping numbers, it can be solved without requiring additional space by using a simple mathematical approach. Here's how you can do it in Python:

def swap_numbers(a, b): # a = 9, b = 4
    a = a + b # a = 13
    b = a - b # b = 9
    a = a - b # a = 4
    return a, b