Last active
October 10, 2024 03:28
-
-
Save jackstine/c5d15e72be80240f208ee84224532423 to your computer and use it in GitHub Desktop.
Heap using merge K sorted List Nodes
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "container/heap" | |
| "fmt" | |
| ) | |
| type ListNode struct { | |
| Val int | |
| Next *ListNode | |
| } | |
| type ListNodeHeap []*ListNode | |
| func (h ListNodeHeap) Len() int { return len(h) } | |
| func (h ListNodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } | |
| func (h ListNodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val } | |
| func (h *ListNodeHeap) Pop() any { | |
| old := *h | |
| n := len(old) | |
| lastListNode := old[n-1] | |
| if lastListNode.Next == nil { | |
| *h = old[0 : n-1] | |
| } else { | |
| old[n-1] = lastListNode.Next | |
| } | |
| return lastListNode.Val | |
| } | |
| func (h *ListNodeHeap) Push(x any) { | |
| *h = append(*h, x.(*ListNode)) | |
| } | |
| func mergeKLists(lists []*ListNode) *ListNode { | |
| if len(lists) == 0 { | |
| return nil | |
| } else if len(lists) == 1 { | |
| return lists[0] | |
| } else { | |
| listHeap := make(ListNodeHeap, 0, len(lists)) | |
| heap.Init(&listHeap) | |
| for _, l := range lists { | |
| if l != nil { | |
| heap.Push(&listHeap, l) | |
| } | |
| } | |
| var head, currentNode *ListNode | |
| for listHeap.Len() > 0 { | |
| value := heap.Pop(&listHeap) | |
| heap.Fix(&listHeap, listHeap.Len()-1) | |
| if head == nil { | |
| head = &ListNode{ | |
| Val: value.(int), | |
| } | |
| currentNode = head | |
| } else { | |
| currentNode.Next = &ListNode{ | |
| Val: value.(int), | |
| } | |
| currentNode = currentNode.Next | |
| } | |
| } | |
| return head | |
| } | |
| } | |
| // func mergeKLists(lists []*ListNode) *ListNode { | |
| // if len(lists) == 0 { | |
| // return nil | |
| // } else if len(lists) == 1 { | |
| // return lists[0] | |
| // } else { | |
| // listOfNodes := make([]*ListNode, 0, len(lists)) | |
| // listOfNodes = append(listOfNodes, lists...) | |
| // var mergeSortedList *ListNode | |
| // // do the thing | |
| // for { | |
| // currentTopValueOfHeap := 1 | |
| // newListOfNodes := make([]*ListNode, 0, len(listOfNodes)) | |
| // for _, l := range listOfNodes { | |
| // currentNode := l | |
| // if currentNode == nil { | |
| // continue | |
| // } | |
| // for currentNode != nil { | |
| // value := currentNode.Val | |
| // if value < currentTopValueOfHeap { | |
| // // insert the value into the heap | |
| // } else { | |
| // break | |
| // } | |
| // currentNode = currentNode.Next | |
| // } | |
| // if currentNode != nil { | |
| // newListOfNodes = append(newListOfNodes, currentNode) | |
| // } | |
| // listOfNodes = newListOfNodes | |
| // } | |
| // // for each value on the heap | |
| // // add to the mergeSortedList the head | |
| // mergeSortedList := | |
| // } | |
| // } | |
| // } | |
| func run(nums [][]int) { | |
| nodes := make([]*ListNode, 0, len(nums)) | |
| for _, num := range nums { | |
| nodes = append(nodes, genListNode(num)) | |
| } | |
| printListNode(mergeKLists(nodes)) | |
| } | |
| func printListNode(head *ListNode) { | |
| currentNode := head | |
| for currentNode != nil { | |
| fmt.Print(currentNode.Val) | |
| currentNode = currentNode.Next | |
| } | |
| fmt.Println() | |
| } | |
| func genListNode(nums []int) *ListNode { | |
| var prev, root *ListNode | |
| for i, n := range nums { | |
| node := &ListNode{Val: n} | |
| if i == 0 { | |
| root = node | |
| prev = root | |
| } else { | |
| prev.Next = node | |
| prev = node | |
| } | |
| } | |
| return root | |
| } | |
| func main() { | |
| values := [][]int{{1, 4, 5}, {1, 3, 4}, {2, 6}} | |
| run(values) | |
| values = [][]int{} | |
| run(values) | |
| values = [][]int{{}} | |
| run(values) | |
| values = [][]int{{}, {}} | |
| run(values) | |
| values = [][]int{{1, 2, 2}, {1, 1, 2}} | |
| run(values) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment