Question

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

My idea

Compare the link node value to determine what should pointer point to.

Highlights

VALUE = node.next means VALUE point to the node's next object
node.next = VALUE means the node's next object is VALUE

My code

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        dummy = head
        while l1 and l2:
            if l1.val >= l2.val:
                dummy.next = l2 #把当前节点挂到合并好的链表dummy上
                l2 = l2.next  #把待合并的链表的最开始节点的指针后移
            else:
                dummy.next = l1
                l1 = l1.next
            dummy = dummy.next
        if l1:
            dummy.next = l1
        if l2:
            dummy.next = l2
        
        return head.next

Better idea

Recursion

Code

class Solution:
    def mergeTwoLists(self, l1, l2):
        if not l1 or not l2:
            return l1 or l2
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2