程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Merge k Sorted Lists

LeetCode Merge k Sorted Lists

編輯:C++入門知識

LeetCode Merge k Sorted Lists


LeetCode解題之Merge k Sorted Lists


原題

將k個有序的鏈表拼接成一個有序的鏈表。

注意點:

Python中有自帶的堆排序實現heapq

例子:

輸入: lists = [[1->2>10],[3->9],[5->6]]
輸出: 1->2->3->5->6->9->10

解題思路

整體思路與Merge Two Lists相同。不過就是從原來的兩個數中取最小的節點改為從k個數中取最小的節點。這是一個典型的堆排序的應用,Python中堆排序可以用heapq實現。

AC源碼

import heapq


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


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            if node:
                heapq.heappush(heap, (node.val, node))

        temp = ListNode(-1)
        head = temp
        while heap:
            smallestNode = heapq.heappop(heap)[1]
            temp.next = smallestNode
            temp = temp.next
            if smallestNode.next:
                heapq.heappush(heap, (smallestNode.next.val, smallestNode.next))
        return head.next

歡迎查看我的Github來獲得相關源碼。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved