[LeetCode&Python] Problem 21. Merge Two Sorted Lists

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

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def mergeTwoLists(self, l1, l2):

        """

        :type l1: ListNode

        :type l2: ListNode

        :rtype: ListNode

        """

        if not l1 and l2:

            return l2

        if not l2 and l1:

            return l1

        if not l1 and not l2:

            return []

        it1=l1

        it2=l2

        if it1.val<=it2.val:

            node=ListNode(it1.val)

            it1=it1.next

        else:

            node=ListNode(it2.val)

            it2=it2.next

        ll=node

        while it1 and it2:

            if it1.val<=it2.val:

                node1=ListNode(it1.val)

                it1=it1.next

                node.next=node1

                node=node1

            else:

                node1=ListNode(it2.val)

                node.next=node1

                node=node1

                it2=it2.next

        if it1:

            node.next=it1

        elif it2:

            node.next=it2

        return ll