剑指 Offer 25. 合并两个排序的链表

题目描述

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

解题思路

1.迭代法：
使用双指针，不断遍历l1和l2，选一个val较小的节点作为node，一直遍历到l1或l2为None，这时候node接上不为None的一条就可以了。
可以使用原地法，节约内存。
2.递归法：
每次的next都返回接下来两条链中比较小的那个节点。

解题代码

迭代法：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = None
        head_flag = True
        node = None
        pre_node = None
        # 如果l1或l2为空，直接返回另一条就行
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        while l1 is not None and l2 is not None:
            if l1.val >= l2.val:
                node = l2
                l2 = l2.next
            elif l1.val < l2.val:
                node = l1
                l1 = l1.next
            # 如果是第一个节点的话，要记录下来；如果不是，要设置一下pre_node.next
            if head_flag is True:
                head = node
                head_flag = False
            else:
                pre_node.next = node
            pre_node = node
        # 遍历到一条的尾巴，直接把剩下那一条接上去
        if l1 is None:
            pre_node.next = l2
        elif l2 is None:
            pre_node.next = l1
        return head

递归法：

class Solution:
    def mergeTwoLists(self, node1: ListNode, node2: ListNode) -> ListNode:
        if node1 is None:
            return node2
        elif node2 is None:
            return node1
        if node1.val >= node2.val:
            node2.next = self.mergeTwoLists(node1, node2.next)
            return node2
        elif node1.val < node2.val:
            node1.next = self.mergeTwoLists(node1.next, node2)
            return node1

关键点

不要忘了设立pre_node和start_node。

执行结果

迭代法：68ms 15.3MB
递归法：76ms 17MB