Merge K ascending linked lists

Topic describes

You are given an array of linked lists, each of which has been sorted in ascending order.

Please merge all lists into one ascending list and return the merged list.

Their thinking

algorithm

Multiple merge, small top heap

Train of thought

We use the small top heap to maintain the list head node that stores the minimum value

Insert all the list head nodes into the heap first

One thing to note here is that we’re maintaining the small top heap, filling in the list nodes, and the comparison function is comparing the values of the nodes

Then constantly extract the head node to merge it into the new linked list (RET)

After the merge, we need to see if the popup header, cur, exists in cur.next, and if there are any subsequent elements, we need to insert them into the heap, and continue as long as there are elements in the heap

Finally, ret.next, the head node of the new list, is returned

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
      / * * *@param {ListNode[]} lists
       * @return {ListNode}* /

      // list, heap, merge sort

      function ListNode(val, next) {
        this.val = val === undefined ? 0 : val
        this.next = next === undefined ? null : next
      }
      const l1 = new ListNode(1.new ListNode(4.new ListNode(5)))
      const l2 = new ListNode(1.new ListNode(3.new ListNode(4)))
      const l3 = new ListNode(2.new ListNode(6))

      var mergeKLists = function (lists) {
        // The priority queue stores the current positions of all k lists
        const h = new Heap((a, b) = > {
          if(! b)return false
          return a.val > b.val
        })

        // queue k linked list heads in sequence
        for (x of lists) {
          if(! x)continue
          h.insert(x)
        }

        // Continuously pop nodes from h and put them at the end of the merged list
        let ret = new ListNode(),
          p = ret
        while(! h.isEmpty()) {const cur = h.extract()
          p.next = cur
          p = p.next

          // If cur.next exists, i.e. the current popup node has a next node, we need to put it into h
          if (cur.next) {
            h.insert(cur.next)
          }
        }

        return ret.next
      }

      class Heap {
        constructor(compareFn) {
          this.compareFn = compareFn
          this.heap = []
        }

        swap(parent, index) {
          const arr = this.heap ; [arr[parent], arr[index]] = [arr[index], arr[parent]] }getLeftIndex(index) {
          return index * 2 + 1
        }

        getRightIndex(index) {
          return index * 2 + 2
        }

        getParentIndex(index) {
          return Math.floor((index - 1) / 2)}size() {
          return this.heap.length
        }

        isEmpty() {
          return this.size() === 0
        }

        insert(value) {
          const index = this.heap.length
          this.heap.push(value)

          this.siftUp(index)
        }

        siftUp(index) {
          let parent = this.getParentIndex(index)

          while (
            index > 0 &&
            this.compareFn(this.heap[parent], this.heap[index])
          ) {
            this.swap(parent, index)
            index = parent
            parent = this.getParentIndex(index)
          }
        }

        extract() {
          if (this.isEmpty()) return
          if (this.size() === 1) return this.heap.pop()

          const removedItem = this.heap[0]
          this.heap[0] = this.heap.pop()
          this.siftDown(0)

          return removedItem
        }

        siftDown(index) {
          let element = index
          const left = this.getLeftIndex(index)
          const right = this.getRightIndex(index)

          if (
            index < this.size() &&
            this.compareFn(this.heap[element], this.heap[left])
          ) {
            element = left
          }

          if (
            index < this.size() &&
            this.compareFn(this.heap[element], this.heap[right])
          ) {
            element = right
          }

          if(element ! == index) {this.swap(element, index)
            this.siftDown(element)
          }
        }

        top() {
          return this.heap[0]}}Copy the code