[LeetCode] 021. Merge Two Sorted List

April 01, 2019 - Monday

Algorithm

leetcode

python

Problem (Easy)
Approach 1: Read - Sort - Write
- Idea
- Solution
- Complexity

Problem (Easy)

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

Approach 1: Read - Sort - Write

Idea

Read both linked list integers out and save into a list, sort it and write the new list back into a linked list.

Solution

class Solution1:
    def mergeTwoLists(self, l1, l2):
        """ 
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l = []
        while l1: 
            l.append(l1.val)
            l1 = l1.next
        while l2: 
            l.append(l2.val)
            l2 = l2.next
        l.sort()
        head = None
        for n in l:
            if not head:
                head = ListNode(n)
                tmp = head
            else:
                tmp.next = ListNode(n)
                tmp = tmp.next
    
        return head

Complexity

Time: $O(log(L1+L2))$?
Space: $O(L1+L2)$