合并两个有序链表

Leetcode Link: 21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com) 剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解法一

思路：双指针

题解：

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
 
        newList = ListNode()
        newHead = newList #记录新的dummy node 的 head
 
        while(list1!=None and list2!=None):
            if list1.val >= list2.val:
                newList.next = list2
                newList = newList.next
                list2 = list2.next
            else:
                newList.next = list1
                newList = newList.next
                list1 = list1.next
                
		# 这里可以直接接过来，省了两个循环
        if list1==None:
            newList.next = list2
        else:
            newList.next = list1
        # 注意这里的返回值
        return newHead.next
 

解法二

思路：题解链接

对于此题，需要思考返回是什么，怎么利用返回值。

在本题中，似乎我们递归只能通过 . next 往下走，因此我们可以猜测，base case 就是当某一个链表走到头的时候，返回一个值。

猜测至此，似乎可以感觉出来了，我们不断递归两个链表还没看过的部分，返回排序好的链表。

题解：

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 == None:
            return list2
        if list2 == None:
            return list1
        dummy = ListNode()
        if list1.val <= list2.val:
            dummy.next = list1
            dummy.next.next =self.mergeTwoLists(list1.next, list2)
        else:
            dummy.next = list2
            dummy.next.next = self.mergeTwoLists(list1, list2.next)
        return dummy.next

Note

开始想不通如果每个递归都制作一个 dummy，最后岂不是会有很多没用的指针？ 其实返回 dummy.next 就够了。 一定记得在每次递归的时候将结果和当前的链表拼上。

启发和联系

将剩下的链表接到新的链表中，可以直接用.next指向剩下的链表，而不需要一个一个复制。这样可以省下两个循环。