Merge Two Sorted Lists

Linked List
Easy

Approach

Diagrams

Analysis

Time

O(n + m)

Space

O(1)
class Solution:
    def mergeTwoLists(self, mainList, otherList):
        if not (mainList or otherList):
            return None

        if not mainList:
            return otherList

        if not otherList:
            return mainList

        mainPointer = mainList
        otherPointer = otherList
        prevPointer = None

        while mainPointer and otherPointer:
            if mainPointer.val < otherPointer.val:
                prevPointer = mainPointer
                mainPointer = mainPointer.next

            else:
                if prevPointer is not None:
                    prevPointer.next = otherPointer

                prevPointer = otherPointer
                otherPointer = otherPointer.next
                prevPointer.next = mainPointer

        if not mainPointer:
            prevPointer.next = otherPointer

        return mainList if mainList.val < otherList.val else otherList

Learn

#Linked List

Videos