04_合并两个有序链表

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


# 自己做的 20ms
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        解题思路：遍历两个链表，取最小值依次append到一个列表
                 遍历这个列表 生成需要的链表
        """
        temp1 = l1
        temp2 = l2
        nodelist = []
        if not l1:
            return l2
        if not l2:
            return l1

        while True:
            if temp1 is None or temp2 is None:
                break
            if temp1.val < temp2.val:
                nodelist.append(temp1.val)
                temp1 = temp1.next
                lastnode = temp2
            else:
                nodelist.append(temp2.val)
                temp2 = temp2.next
                lastnode = temp1

        for i in range(len(nodelist)):
            if i == 0:
                new_listnode = ListNode(nodelist[i])
                new_head = new_listnode
            else:
                new_listnode.next = ListNode(nodelist[i])
                new_listnode = new_listnode.next

        new_listnode.next = lastnode
        return new_head


# leetcode上最优解 8ms 我是创建新的有序列表 它是直接创建新的有序链表 判断完大小后不append到列表，直接拼接到新的链表后面
class Solution2(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None and l2 is not None:
            return l2
        if l1 is not None and l2 is None:
            return l1
        if l1 == l2 is None:
            return None

        i = l1
        j = l2
        dummy_head = ListNode(-1)
        end = dummy_head

        while i is not None and j is not None:

            if i.val <= j.val:
                tmp1 = i.next
                end.next = i
                end = i
                i = tmp1
            elif i.val > j.val:
                tmp2 = j.next
                end.next = j
                end = j
                j = tmp2

        while i is None and j is not None:
            tmp2 = j.next
            end.next = j
            end = j
            j = tmp2

        while i is not None and j is None:
            tmp1 = i.next
            end.next = i
            end = i
            i = tmp1

        return dummy_head.next


# leetcode 最优解 自己改进版 减少了代码量
# 结合了我自己写的lastnode变量 因为如果一个到头了，直接把另一个剩下的挂到新链表的后面就行，不用再遍历加入了
class Solution3(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None and l2 is not None:
            return l2
        if l1 is not None and l2 is None:
            return l1
        if l1 == l2 is None:
            return None

        i = l1
        j = l2
        dummy_head = ListNode(-1)
        end = dummy_head

        while i is not None and j is not None:

            if i.val <= j.val:
                tmp1 = i.next
                end.next = i
                end = i
                i = tmp1
                lastnode = j
            elif i.val > j.val:
                tmp2 = j.next
                end.next = j
                end = j
                j = tmp2
                lastnode = i

        # while i is None and j is not None:
        #     tmp2 = j.next
        #     end.next = j
        #     end = j
        #     j = tmp2
        #
        # while i is not None and j is None:
        #     tmp1 = i.next
        #     end.next = i
        #     end = i
        #     i = tmp1
        end.next = lastnode

        return dummy_head.next


a = ListNode(1)
b = ListNode(2)
c = ListNode(4)
d = ListNode(1)
e = ListNode(3)
f = ListNode(4)
a.next = b
b.next = c

d.next = e
e.next = f
s = Solution()
s.mergeTwoLists(a, d)