[剑指offer]25.合并两个排序的链表(迭代+递归)

25.合并两个排序的链表

题目

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

方法一 迭代

时间复杂度O(n1+n2)，空间复杂度O(1)

思路: 令cur = dum，不断比较l1与l2当前节点的值，并将更小值赋给cur，最后返回没有遍历完的链表

oj代码

class Solution():

    def mergeTwoLists(self, l1, l2):

        cur = dum = ListNode(0)

        while l1 and l2:

            if l1.val < l2.val:

                cur.next, l1 = l1, l1.next

            else:

                cur.next, l2 = l2, l2.next

            cur = cur.next

        cur.next = l1 if l1 else l2

        return dum.next

if __name__ == "__main__":

    node1 = ListNode(1)

    node2 = ListNode(2)

    node3 = ListNode(3)

    node4 = ListNode(4)

    node5 = ListNode(5)

    node1.next = node2

    node2.next = node3

    node3.next = node4

    node4.next = node5

    n1 = ListNode(6)

    n2 = ListNode(7)

    n3 = ListNode(8)

    n1.next = n2

    n2.next = n3

    res = Solution().mergeTwoLists(node1, n1)

    cur = res

    while cur:

        print(cur.val)

        cur = cur.next

方法二 递归

时间复杂度O(n1+n2)，空间复杂度O(1)

思路：比较l1与l2节点值，将更小值的指针指向下一个更小值。并返回当前节点值。

class Solution:

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

        if not l1:

            return l2

        if not l2:

            return l1

        if l1.val < l2.val:

            l1.next = self.mergeTwoLists(l1.next, l2)

            return l1

        else:

            l2.next = self.mergeTwoLists(l1, l2.next)

            return l2