Skip to main content

Merge Two Sorted Lists

Question​

Given two sorted linked lists, write a function to merge the two sorted lists into a single sorted list.

Example 1
Input: 
list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]

Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Solution​

all//Merge Two Sorted Lists.py


# 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, l1, l2):
        if not l1 and not l2:
            return None
        if not l1:
            return l2
        if not l2:
            return l1

        head = ListNode()
        node = head

        while l1 and l2:
            if l1.val < l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next

        if l1:
            node.next = l1
        else:
            node.next = l2

        return head.next