“This is the 20th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

describe

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [].enlighened by [1 4], [2, 6]] Output:,1,2,3,4,4,5,6 [1] Explanation: The linked - lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6Copy the code

Note:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won't exceed 10^4.
Copy the code

parsing

Given a list of K linked lists, each list is sorted in ascending order. Merges all lists into a sorted list and returns. Because k is at most 10^4, and each list is at most 500, traversal time O(10^6) will not time out, within O(N), And then the total time of sorting is O(NlogN), which still works.

We first use a list nodes to store the values of the left and right nodes, and then iterate over all the linked list nodes. After obtaining the new nodes, we sort them in ascending order. We define a head node, point/result, to iterate over each value in nodes and convert the value of the node to ListNode type. And then you can concatenate the point pointer. At the end of the loop we just need to return result.next. Space complexity is O(N).

In fact, this solution is more clever, we are in a tight time in the competition, if the restriction conditions are not strict, it can be solved in this way, but in the usual training process alone or use other solutions to solve the problem.

answer

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        nodes = []
        for l in lists:
            while l:
                nodes.append(l.val)
                l = l.next
        point = result = ListNode(0)
        for node in sorted(nodes):
            point.next = ListNode(node)
            point = point.next
        return result.next
Copy the code

The results

Given Lists in Python online submissions. Sorted Lists 22.3 MB, less than 36.77% of Python online submissions for Merge k Sorted ListsCopy the code

The original link

Leetcode.com/problems/me…

Your support is my biggest motivation