转自Kindem的博客

题目

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

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

大意是给出两个已经排完序的链表，将它们合成一个排序完的链表

解题思路

构建一个新链表，一边构建，一边从原来的链表中取数据

python3代码:

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l = ListNode(0)
        x = l
        p = l1
        q = l2
        while p or q:
            if not p:
                x.next = ListNode(q.val)
                q = q.next
                x = x.next
                continue
            if not q:
                x.next = ListNode(p.val)
                p = p.next
                x = x.next
                continue
            else:
                x.next = ListNode(min(p.val, q.val))
                if p.val < q.val:
                    p = p.next
                else:
                    q = q.next
            x = x.next
        return l.next