{"id":5122,"date":"2021-09-21T07:46:42","date_gmt":"2021-09-21T07:46:42","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5122"},"modified":"2022-12-14T07:19:49","modified_gmt":"2022-12-14T07:19:49","slug":"merge-k-sorted-linked-lists-set-2-using-min-heap","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/","title":{"rendered":"Merge k sorted linked lists | Set 2 (Using Min Heap)"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png\" alt=\"\" \/><\/p>\n<p>Several approaches exist in the programming world to solve this problem, some efficient and some not so efficient. Let us build the intuition to solve this problem brick by brick, by first discussing some simple methods, which are not so efficient. In this blog, we will see the problem merge k sorted lists using heap.  <\/p>\n<h2>How to Merge K Sorted Lists using Heap <\/h2>\n<p>In this problem, we will be given K sorted linked lists. We need to merge all the lists such that the newly created list is also in sorted order.<\/p>\n<p>The problem statement is quite straightforward, we will be given K sorted linked lists, and then we need to form a linked list using the nodes of all the given linked lists such that the newly formed list is sorted in order. <\/p>\n<p>Let&#8217;s try to understand the problem with the help of examples:<br \/>\nIf the sorted lists given to us are:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/input-18.png\" alt=\"\" \/><\/p>\n<ul>\n<li>According to the problem statement, we need to merge all these given linked lists into a single linked list in such a way that after merging, the final linked list is sorted in nature.<\/li>\n<li>The list that we need to return must contain all the nodes of all three given lists in sorted order.<\/li>\n<li>So, after merging the newly formed sorted list will be:<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/output-17.png\" alt=\"\" \/><\/p>\n<p>Let\u2019s take another example:<br \/>\nIf the sorted lists given to us be 2\u21928\u21929\u219210\u2192NULL, 11\u219213\u219217\u2192NULL.<\/p>\n<ul>\n<li>In this case, after merging, the final resultant sorted linked list will be 2\u21928\u21929\u219210\u219211\u219213\u219217\u2192NULL.<\/li>\n<\/ul>\n<p>At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.<\/p>\n<p>Before moving to the approach section, try to think about how you can approach this problem.<\/p>\n<ul>\n<li>If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.<\/li>\n<\/ul>\n<p>Let\u2019s move to the approach section.<\/p>\n<h2>Approach of how to merge k sorted lists using heap <\/h2>\n<p>In this approach, we will be using min heap.<\/p>\n<ul>\n<li>First, we need to create a min-heap.<\/li>\n<li>Since the smallest elements are present at the beginning of each list as each of them is sorted, so, we need to insert each list\u2019s first element in our heap.<\/li>\n<li>Now, while our heap is not empty, we need to take out its top element and attach it at the end of our result list.<\/li>\n<li>The node which we attached to the end of the result list will be from one of the <strong>K<\/strong> given linked list, so if the next node of the node which we attached at the end of the result list exists, we need to push it into the min heap. <\/li>\n<li>Finally, when our <strong>min heap<\/strong> is empty, at that time the result list will contain all the nodes of the <strong>K<\/strong> given linked list in sorted order.<\/li>\n<\/ul>\n<h2>Algorithm of how to merge k sorted lists using heap <\/h2>\n<ul>\n<li>Write a comparator function for the priority queue to store minimum elements at the top.<\/li>\n<li>Push starting node of all the lists in the min-heap.<\/li>\n<li>Now, create a node <strong>head<\/strong> with zero value that will act as a dummy node for our newly created list.<\/li>\n<li>Initialize a <strong>temp<\/strong> variable with the address of the above-created node.<\/li>\n<li>Run a while loop till the priority queue size is greater than 0.<\/li>\n<li>Store the topmost element of the queue into a variable, say <strong>p<\/strong>.<\/li>\n<li>Now remove the top element from the priority queue.<\/li>\n<li>Attach the node <strong>p<\/strong> at the end of our new list by doing <strong>temp-&gt;next  = p<\/strong>.<\/li>\n<li>Now advance the temp variable by one node i.e, <strong>temp = temp-&gt;next<\/strong>.<\/li>\n<li>If the node after <strong>p<\/strong> is not NULL, push the node after <strong>p<\/strong> into the priority queue.<\/li>\n<li>After the completion of the while loop, return <strong>head-&gt;next<\/strong>, as it will be the first node of our newly created linked list.<\/li>\n<\/ul>\n<h3>Dry Run of how to merge k sorted lists using heap <\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_1-15.png\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_2-16.png\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_3-9.png\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_4-5.png\" alt=\"\" \/><\/p>\n<h2>Code Implementation of how to merge k sorted lists using heap<\/h2>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5124 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_5124 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_5124 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5124 .wpsm_nav-tabs > li.active > a, #tab_container_5124 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5124 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_5124 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_5124 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5124 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5124 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5124 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5124 .wpsm_nav-tabs > li > a:hover , #tab_container_5124 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_5124 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_5124 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_5124 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_5124 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_5124 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_5124 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_5124 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5124 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_5124 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5124 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_5124 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_5124\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5124\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5124_1\" aria-controls=\"tabs_desc_5124_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5124_2\" aria-controls=\"tabs_desc_5124_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_5124_3\" aria-controls=\"tabs_desc_5124_3\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_5124\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_5124_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include&lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n\r\n\/\/ class with constructor for a node of Linked list\r\nclass Node {\r\n    public:\r\n    int data;\r\n    Node* next;\r\n    \/\/ constructor\r\n    Node(int x){\r\n        data = x;\r\n        next = NULL;\r\n}\r\n};\r\n\/\/ This function prints data of the linked list\r\nvoid print(Node* head)\r\n{\r\n    Node* curr = head;\r\n    while (curr != NULL) {\r\n        cout &lt;&lt; curr-&gt;data &lt;&lt; &quot; -&gt; &quot;;\r\n        curr = curr-&gt;next;\r\n    }\r\n    cout&lt;&lt;&quot;NULL&quot;;\r\n}\r\n\r\n\/\/ this is the comparator function for the priority queue to\r\n\/\/ make it behave as a min-heap\r\nstruct compare\r\n{\r\n    bool operator()(Node* &amp;a,Node* &amp;b)\r\n    {\r\n        return a-&gt;data&gt;b-&gt;data;\r\n    }\r\n};\r\n\r\n\/\/ This function merges 'K' sorted lists into one sorted list\r\nNode* mergeKLists(Node* arr[], int back)\r\n{\r\n    priority_queue&lt;Node*,vector&lt;Node*&gt;,compare&gt;minh;\r\n    for(int i=0;i&lt;=back;i++)\r\n    {\r\n        if(arr[i]!=NULL) minh.push(arr[i]);\r\n    }\r\n    Node* head=new Node(0);\r\n    Node* temp=head;\r\n    while(minh.size()&gt;0)\r\n    {\r\n        Node* p = minh.top();\r\n        minh.pop();\r\n        temp-&gt;next = p;\r\n        temp=temp-&gt;next;\r\n        if(p-&gt;next!=NULL) minh.push(p-&gt;next);\r\n    }\r\n    return head-&gt;next;\r\n}\r\n\r\n\/\/ main function\r\nint main()\r\n{\r\n    Node * arr[3];\r\n    Node *head = new Node(2);\r\n    head-&gt;next = new Node(3);\r\n    head-&gt;next-&gt;next = new Node(5);\r\n    Node *h2 = new Node(1);\r\n    h2-&gt;next = new Node(4);\r\n    h2-&gt;next-&gt;next = new Node(8);\r\n\r\n    Node *h3 = new Node(6);\r\n    h3-&gt;next = new Node(7);\r\n    h3-&gt;next-&gt;next = new Node(9);\r\n\r\n    arr[0] = head;\r\n    arr[1] = h2;\r\n    arr[2] = h3;\r\n    \r\n    cout&lt;&lt;&quot;Final resultant merged linked list&quot;&lt;&lt;endl;\r\n    print(mergeKLists(arr,2));\r\n    \r\n    return 0;\r\n}\r\n\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_5124_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nimport java.util.*;\r\n\r\nclass Node \r\n{\r\n    int data;\r\n    Node next;\r\n    Node(int key)\r\n    {\r\n        data = key;\r\n        next = null;\r\n    }\r\n}\r\nclass NodeComparator implements Comparator&lt;node&gt; {\r\n\r\n    public int compare(Node k1, Node k2)\r\n    {\r\n        if (k1.data &gt; k2.data)\r\n            return 1;\r\n        else if (k1.data &lt; k2.data)\r\n            return -1;\r\n        return 0;\r\n    }\r\n}\r\nclass MergeKSorted \r\n{\r\n    static Node mergeKList(Node[] arr, int K)\r\n    {\r\n        \/* Priority_queue 'queue' implemented as min heap \r\n        with the help of 'compare' function *\/\r\n        PriorityQueue&lt;node&gt; queue\r\n            = new PriorityQueue&lt;&gt;(new NodeComparator());\r\n        Node at[] = new Node[K];\r\n        Node head = new Node(0);\r\n        Node last = head;\r\n        \/\/ Push the head nodes of all the k lists in 'queue'\r\n        for (int i = 0; i &lt; K; i++) {\r\n            if (arr[i] != null) {\r\n                queue.add(arr[i]);\r\n            }\r\n        }\r\n        \/\/ Handles the case when k = 0 or lists have no elements in them\r\n        if (queue.isEmpty())\r\n            return null;\r\n        while (!queue.isEmpty()) \r\n        {\r\n            Node curr = queue.poll();\r\n            last.next = curr;\r\n            last = last.next;\r\n            if (curr.next != null) \r\n            {\r\n                queue.add(curr.next);\r\n            }\r\n        }\r\n        return head.next;\r\n    }\r\n    public static void printList(Node node)\r\n    {\r\n        while (node != null) {\r\n            System.out.print(node.data + &quot; &quot;);\r\n            node = node.next;\r\n        }\r\n    }\r\n    public static void main(String[] args)\r\n    {\r\n        int N = 4;\r\n        \/\/ array to store head of linkedlist\r\n        Node[] a = new Node[N];\r\n        \/\/ Linkedlist1\r\n        Node head1 = new Node(1);\r\n        a[0] = head1;\r\n        head1.next = new Node(2);\r\n        head1.next.next = new Node(3);\r\n        \/\/ Limkedlist2\r\n        Node head2 = new Node(4);\r\n        a[1] = head2;\r\n        head2.next = new Node(5);\r\n        \/\/ Linkedlist3\r\n        Node head3 = new Node(5);\r\n        a[2] = head3;\r\n        head3.next = new Node(6);\r\n        \/\/ Linkedlist4\r\n        Node head4 = new Node(7);\r\n        a[3] = head4;\r\n        head4.next = new Node(8);\r\n\r\n        Node res = mergeKList(a, N);\r\n\r\n        if (res != null)\r\n            printList(res);\r\n        System.out.println();\r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_5124_3\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nimport heapq\r\nfrom heapq import heappop, heappush\r\n \r\n \r\n# A Linked List Node\r\nclass Node:\r\n    def __init__(self, data, next=None):\r\n        self.data = data\r\n        self.next = next\r\n \r\n    # Override the `__lt__()` function to make `Node` class work with min-heap\r\n    def __lt__(self, other):\r\n        return self.data &lt; other.data\r\n \r\n \r\n# Utility function to print contents of a linked list\r\ndef printList(node):\r\n    while node:\r\n        print(node.data, end=' ')\r\n        node = node.next\r\n \r\n \r\n# The main function to merge given `k` sorted linked lists.\r\n# It takes a list of lists `list` of size `k` and generates the sorted output\r\ndef mergeKLists(lists):\r\n \r\n    # create a min-heap using the first node of each list\r\n    pq = [x for x in lists]\r\n    heapq.heapify(pq)\r\n \r\n    # take two pointers, head and tail, where the head points to the first node\r\n    # of the output list and tail points to its last node\r\n    head = last = None\r\n \r\n    # run till min-heap is empty\r\n    while pq:\r\n \r\n        # extract the minimum node from the min-heap\r\n        min = heappop(pq)\r\n \r\n        # add the minimum node to the output list\r\n        if head is None:\r\n            head = min\r\n            last = min\r\n        else:\r\n            last.next = min\r\n            last = min\r\n \r\n        # take the next node from the &quot;same&quot; list and insert it into the min-heap\r\n        if min.next:\r\n            heappush(pq, min.next)\r\n \r\n    # return head node of the merged list\r\n    return head\r\n \r\n \r\nif __name__ == '__main__':\r\n \r\n    # total number of linked lists\r\n    k = 3\r\n \r\n    # a list to store the head nodes of the linked lists\r\n    lists = [None] * k\r\n \r\n    lists[0] = Node(2)\r\n    lists[0].next = Node(3)\r\n    lists[0].next.next = Node(5)\r\n \r\n    lists[1] = Node(1)\r\n    lists[1].next = Node(4)\r\n    lists[1].next.next = Node(8)\r\n \r\n    lists[2] = Node(6)\r\n    lists[2].next = Node(7)\r\n    lists[2].next.next = Node(9)\r\n \r\n    head = mergeKLists(lists)\r\n    printList(head)\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_5124 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_5124 a\"),jQuery(\"#tab-content_5124\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<pre><code>Output\nFinal resultant merged linked list\n1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL<\/code><\/pre>\n<p><strong>Time Complexity of how to merge k sorted lists using heap :<\/strong> O(NKlog(K)), <strong>N<\/strong> is the number of nodes in the list, and <strong>K<\/strong> is the total number of lists.<\/p>\n<p><strong>Conclusion<\/strong><\/p>\n<p>This blog tried to explain the merge k sorted lists using heap  This problem tests a candidate&#8217;s problem-solving skills and his or her grasp on the concepts of linked list and heap. We highly encourage you to have a good grasp of major data structures. If you want to practice more questions on linked lists, feel free to solve them at  Prepbytes <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n<h2>FAQs related to how to merge k sorted lists using heap<\/h2>\n<p><strong>1. What is the time complexity of merging two sorted lists?<\/strong><br \/>\nThe complexity is O(m log n). There are m iterations of the loop. Each insertion into a sorted array is an O(log n) operation. Therefore the overall complexity is O (m log n).<\/p>\n<p><strong>2. What is the algorithm for merge sort?<\/strong><br \/>\nThe Merge Sort algorithm is a sorting algorithm that is based on the Divide and Conquers paradigm. In this algorithm, the array is initially divided into two equal halves and then they are combined in a sorted manner.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Several approaches exist in the programming world to solve this problem, some efficient and some not so efficient. Let us build the intuition to solve this problem brick by brick, by first discussing some simple methods, which are not so efficient. In this blog, we will see the problem merge k sorted lists using heap. [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[125],"tags":[],"class_list":["post-5122","post","type-post","status-publish","format-standard","hentry","category-linked-list"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Merge k sorted linked lists - Set 2 (Using Min Heap) | Linked List | Prepbytes<\/title>\n<meta name=\"description\" content=\"Learn how to merge K sorted linked lists using min-heap.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Merge k sorted linked lists - Set 2 (Using Min Heap) | Linked List | Prepbytes\" \/>\n<meta property=\"og:description\" content=\"Learn how to merge K sorted linked lists using min-heap.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-09-21T07:46:42+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-12-14T07:19:49+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Merge k sorted linked lists | Set 2 (Using Min Heap)\",\"datePublished\":\"2021-09-21T07:46:42+00:00\",\"dateModified\":\"2022-12-14T07:19:49+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/\"},\"wordCount\":870,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/\",\"name\":\"Merge k sorted linked lists - Set 2 (Using Min Heap) | Linked List | Prepbytes\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png\",\"datePublished\":\"2021-09-21T07:46:42+00:00\",\"dateModified\":\"2022-12-14T07:19:49+00:00\",\"description\":\"Learn how to merge K sorted linked lists using min-heap.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linked list articles\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/linked-list\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Merge k sorted linked lists | Set 2 (Using Min Heap)\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Merge k sorted linked lists - Set 2 (Using Min Heap) | Linked List | Prepbytes","description":"Learn how to merge K sorted linked lists using min-heap.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/","og_locale":"en_US","og_type":"article","og_title":"Merge k sorted linked lists - Set 2 (Using Min Heap) | Linked List | Prepbytes","og_description":"Learn how to merge K sorted linked lists using min-heap.","og_url":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-09-21T07:46:42+00:00","article_modified_time":"2022-12-14T07:19:49+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Merge k sorted linked lists | Set 2 (Using Min Heap)","datePublished":"2021-09-21T07:46:42+00:00","dateModified":"2022-12-14T07:19:49+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/"},"wordCount":870,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/","url":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/","name":"Merge k sorted linked lists - Set 2 (Using Min Heap) | Linked List | Prepbytes","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png","datePublished":"2021-09-21T07:46:42+00:00","dateModified":"2022-12-14T07:19:49+00:00","description":"Learn how to merge K sorted linked lists using min-heap.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007401524-Article_156.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists-set-2-using-min-heap\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Linked list articles","item":"https:\/\/prepbytes.com\/blog\/category\/linked-list\/"},{"@type":"ListItem","position":3,"name":"Merge k sorted linked lists | Set 2 (Using Min Heap)"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5122","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=5122"}],"version-history":[{"count":6,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5122\/revisions"}],"predecessor-version":[{"id":10692,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5122\/revisions\/10692"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=5122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=5122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=5122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}