{"id":5080,"date":"2021-09-20T06:35:33","date_gmt":"2021-09-20T06:35:33","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5080"},"modified":"2022-04-20T20:18:57","modified_gmt":"2022-04-20T20:18:57","slug":"merge-two-sorted-linked-lists","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/","title":{"rendered":"Merge two sorted linked lists"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png\" alt=\"\" \/><\/p>\n<h3>Introduction<\/h3>\n<p>The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.<\/p>\n<\/p>\n<h3>Problem Statement<\/h3>\n<p>In this problem, we will be given two sorted linked lists. We need to merge both lists such that the newly created list is also in sorted order.<\/p>\n<h3>Problem Statement Understanding<\/h3>\n<p>The problem statement is quite straightforward, we will be given two linked lists that are sorted in nature, and then we need to form a linked list using all the nodes of both 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.<\/p>\n<ul>\n<li>Let the two sorted lists given to us be:<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/input-15.png\" alt=\"\" \/><\/p>\n<ul>\n<li>Now, the list that we need to return must contain all the nodes of both lists in sorted order.<\/li>\n<li>So, the newly formed resultant list will be:<br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/output-14.png\" alt=\"\" \/><br \/>\nLet\u2019s take another example:<\/li>\n<li>Let the two sorted lists given to us be 2\u21928\u21929\u219210\u2192NULL and 11\u219213\u219217\u2192NULL<\/li>\n<li>For the above two sorted lists, the final linked list after merging will be 2\u21928\u21929\u219210\u219211\u219213\u219217\u2192NULL<\/li>\n<\/ul>\n<h5>Some more examples<\/h5>\n<p>Sample Input 1:<\/p>\n<ul>\n<li><strong>list 1:<\/strong> 1\u21923\u21925\u21927<\/li>\n<li><strong>list 2:<\/strong> 2\u21924\u21926\u21928<\/li>\n<\/ul>\n<p>Sample Output 1:<br \/>\n1\u21922\u21923\u21924\u21925\u21926\u21927\u21928<\/p>\n<p>Sample Input 2:<\/p>\n<ul>\n<li><strong>list 1:<\/strong> 2\u21923\u21926\u21927\u21929<\/li>\n<li><strong>list 2:<\/strong> 1\u21925\u21928\u219211\u219219\u219231<\/li>\n<\/ul>\n<p>Sample Output 2:<br \/>\n1\u21922\u21923\u21925\u21926\u21927\u21928\u21929\u219211\u219219\u219231<\/p>\n<p>Now, I think from the above examples, the problem statement is clear. Let\u2019s see how we can approach it.<\/p>\n<p>Before moving to the approach section, try to think 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<h3>Approach 1<\/h3>\n<ul>\n<li>We will make a recursive function that will create a sorted list out of two given sorted lists, containing all the nodes of both the given sorted list.<\/li>\n<li>We will compare the head of both the lists and the one with a smaller head will be appearing at the current position and all other nodes will appear after that.<\/li>\n<li>Now we will call the recursive function for the rest of the remaining nodes, and then we will attach the current node with the result from the recursive call, i.e., with the remaining node\u2019s result.<\/li>\n<li>If any one of the nodes is NULL, then we need to return the other list\u2019s head from there.<\/li>\n<\/ul>\n<p><strong>Time Complexity:<\/strong>  O(n), n is the number of nodes in both the list combined.<br \/>\n<strong>Space Complexity:<\/strong> O(n), n is the size of the recursive stack<\/p>\n<p>The above approach works fine, but can we make our code more efficient in terms of memory. <\/p>\n<ul>\n<li>The answer is yes, and to know how we can reduce the space complexity, read the below approach which uses constant memory.<\/li>\n<\/ul>\n<p>Let\u2019s jump to the next approach.<\/p>\n<h3>Approach 2<\/h3>\n<ul>\n<li>In this approach, we first reverse both the lists given to us as input.<\/li>\n<li>Then we will create an empty list <strong>result<\/strong>.<\/li>\n<li>We will initialize two pointers <strong>h1<\/strong> and <strong>h2<\/strong> to the head of <strong>list 1<\/strong> and <strong>list 2<\/strong>, respectively.<\/li>\n<li>Then we will iterate over both the lists <strong>while(h1 != NULL &amp;&amp; h2!=NULL)<\/strong>.\n<ul>\n<li>While iterating at every step, we will find the larger of the two <strong>h1<\/strong> and <strong>h2<\/strong> by comparing <strong>h1\u2192data<\/strong> and <strong>h2\u2192data<\/strong>.<\/li>\n<li>We will insert the larger one of <strong>h1<\/strong> and <strong>h2<\/strong> at the front of the result list.<\/li>\n<li>Then we will move ahead in the list whose node was larger (larger node &#8211; we will compare using <strong>h1\u2192data<\/strong> and <strong>h2\u2192data<\/strong>).<\/li>\n<\/ul>\n<\/li>\n<li>If any of the <strong>h1<\/strong> or <strong>h2<\/strong> becomes NULL, we will insert all the remaining node\u2019s of the other list into the <strong>result<\/strong> list.<\/li>\n<li>At last, we will have a new list that will be sorted given by <strong>result<\/strong>.<\/li>\n<\/ul>\n<p><strong>Time Complexity:<\/strong> O(n), n is the number of nodes in both the list combined.<br \/>\n<strong>Space Complexity:<\/strong> O(1)<\/p>\n<p>The above approach uses constant space, but it will iterate on both lists two times in the worst case. <\/p>\n<ul>\n<li>First, when the list is reversed and the second time when we are iterating to sort the list. <\/li>\n<\/ul>\n<p>Can we do even better? <\/p>\n<ul>\n<li>The answer is yes, and to know the solution, read the below approach.<\/li>\n<\/ul>\n<h3>Approach 3<\/h3>\n<ul>\n<li>In this approach, we create a <strong>dummy node<\/strong> with INT_MIN value that will represent the <strong>tail<\/strong> of our new list.<\/li>\n<li>Then we will iterate on both the lists while both of them is not NULL.<\/li>\n<li>Then we need to check the node with a smaller value and insert it after the <strong>tail<\/strong> of our new list, and then update the tail of the list.<\/li>\n<li>At last, If the first list has reached NULL, then we need to attach the remaining elements of the second list after the <strong>tail<\/strong> and vice versa.<\/li>\n<\/ul>\n<h3>Algorithm<\/h3>\n<ul>\n<li>Create a node named <strong>dummy<\/strong> having INT_MIN as its data.<\/li>\n<li>Initialize a pointer named <strong>tail<\/strong> with the address of the above-created <strong>dummy<\/strong> variable.<\/li>\n<li>Initialize two pointers named <strong>l1<\/strong> and <strong>l2<\/strong> with the heads of both the lists, respectively.<\/li>\n<li>Until both <strong>l1<\/strong> and <strong>l2<\/strong> are not equal to NULL, run a while loop in which we need to check which pointer points to a smaller node.\n<ul>\n<li>If <strong>l1<\/strong> points to a smaller node, we need to attach <strong>l1<\/strong> at the end of the tail and update <strong>l1<\/strong> with its next node\u2019s address.<\/li>\n<li>If <strong>l2<\/strong> points to a smaller node, we need to attach <strong>l2<\/strong> at the end of the tail and update <strong>l2<\/strong> with its next node\u2019s address<\/li>\n<li>Then, we need to advance the <strong>tail<\/strong> pointer to its next node<\/li>\n<\/ul>\n<\/li>\n<li>After the while loop ends, we need to check whether <strong>l1<\/strong> or <strong>l2<\/strong> is NULL or not.\n<ul>\n<li>If <strong>l2<\/strong> is NULL, we need to assign <strong>tail\u2192next<\/strong> to <strong>l1<\/strong>. <\/li>\n<li>If <strong>l1<\/strong> is NULL, we need to assign <strong>tail\u2192next<\/strong> to <strong>l1<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<li>Finally, we return the <strong>dummy node\u2019s next node<\/strong> as the head of our newly created list.<\/li>\n<\/ul>\n<h3>Dry Run<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_1-10.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_2-11.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_3-5.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_4-1.png\" alt=\"\" \/><\/p>\n<h3>Code Implementation<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5083 {\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_5083 .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_5083 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5083 .wpsm_nav-tabs > li.active > a, #tab_container_5083 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5083 .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_5083 .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_5083 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5083 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5083 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5083 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5083 .wpsm_nav-tabs > li > a:hover , #tab_container_5083 .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_5083 .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_5083 .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_5083 .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_5083 .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_5083 .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_5083 .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_5083 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5083 .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_5083 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5083 .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_5083 .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_5083\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5083\">\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_5083_1\" aria-controls=\"tabs_desc_5083_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_5083_2\" aria-controls=\"tabs_desc_5083_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>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_5083_3\" aria-controls=\"tabs_desc_5083_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>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_5083_4\" aria-controls=\"tabs_desc_5083_4\" 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_5083\">\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_5083_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"c\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include&lt;stdio.h&gt;\r\n#include&lt;stdlib.h&gt;\r\n#include&lt;assert.h&gt;\r\n  \r\n\/* Link list node *\/\r\nstruct Node\r\n{\r\n    int data;\r\n    struct Node* next;\r\n};\r\n  \r\n\/* pull off the front node of the source and put it in dest *\/\r\nvoid MoveNode(struct Node** destRef, struct Node** sourceRef);\r\n  \r\n\/* Takes two lists sorted in increasing order, and splices\r\n   their nodes together to make one big sorted list which\r\n   is returned.  *\/\r\nstruct Node* SortedMerge(struct Node* a, struct Node* b)\r\n{\r\n    \/* a dummy first node to hang the result on *\/\r\n    struct Node dummy;\r\n  \r\n    \/* tail points to the last result node  *\/\r\n    struct Node* tail = &amp;dummy;\r\n  \r\n    \/* so tail-&gt;next is the place to add new nodes\r\n      to the result. *\/\r\n    dummy.next = NULL;\r\n    while (1)\r\n    {\r\n        if (a == NULL)\r\n        {\r\n            \/* if either list runs out, use the\r\n               other list *\/\r\n            tail-&gt;next = b;\r\n            break;\r\n        }\r\n        else if (b == NULL)\r\n        {\r\n            tail-&gt;next = a;\r\n            break;\r\n        }\r\n        if (a-&gt;data &lt;= b-&gt;data)\r\n            MoveNode(&amp;(tail-&gt;next), &amp;a);\r\n        else\r\n            MoveNode(&amp;(tail-&gt;next), &amp;b);\r\n  \r\n        tail = tail-&gt;next;\r\n    }\r\n    return(dummy.next);\r\n}\r\n  \r\n\/* UTILITY FUNCTIONS *\/\r\n\/* MoveNode() function takes the node from the front of the\r\n   source, and move it to the front of the dest.\r\n   It is an error to call this with the source list empty.\r\n  \r\n   Before calling MoveNode():\r\n   source == {1, 2, 3}\r\n   dest == {1, 2, 3}\r\n  \r\n   After calling MoveNode():\r\n   source == {2, 3}\r\n   dest == {1, 1, 2, 3} *\/\r\nvoid MoveNode(struct Node** destRef, struct Node** sourceRef)\r\n{\r\n    \/* the front source node  *\/\r\n    struct Node* newNode = *sourceRef;\r\n    assert(newNode != NULL);\r\n  \r\n    \/* Advance the source pointer *\/\r\n    *sourceRef = newNode-&gt;next;\r\n  \r\n    \/* Link the old dest off the new node *\/\r\n    newNode-&gt;next = *destRef;\r\n  \r\n    \/* Move dest to point to the new node *\/\r\n    *destRef = newNode;\r\n}\r\n  \r\n  \r\n\/* Function to insert a node at the beginning of the\r\n   linked list *\/\r\nvoid push(struct Node** head_ref, int new_data)\r\n{\r\n    \/* allocate node *\/\r\n    struct Node* new_node =\r\n        (struct Node*) malloc(sizeof(struct Node));\r\n  \r\n    \/* put in the data  *\/\r\n    new_node-&gt;data  = new_data;\r\n  \r\n    \/* link the old list off the new node *\/\r\n    new_node-&gt;next = (*head_ref);\r\n  \r\n    \/* move the head to point to the new node *\/\r\n    (*head_ref)    = new_node;\r\n}\r\n  \r\n\/* Function to print nodes in a given linked list *\/\r\nvoid printList(struct Node *node)\r\n{\r\n    while (node!=NULL)\r\n    {\r\n        printf(&quot;%d &quot;, node-&gt;data);\r\n        node = node-&gt;next;\r\n    }\r\n}\r\n  \r\n\/* Driver program to test above functions*\/\r\nint main()\r\n{\r\n    \/* Start with the empty list *\/\r\n    struct Node* res = NULL;\r\n    struct Node* a = NULL;\r\n    struct Node* b = NULL;\r\n  \r\n    \/* Let us create two sorted linked lists to test\r\n      the functions\r\n       Created lists, a: 5-&gt;10-&gt;15,  b: 2-&gt;3-&gt;20 *\/\r\n    push(&amp;a, 15);\r\n    push(&amp;a, 10);\r\n    push(&amp;a, 5);\r\n  \r\n    push(&amp;b, 20);\r\n    push(&amp;b, 3);\r\n    push(&amp;b, 2);\r\n  \r\n    \/* Remove duplicates from linked list *\/\r\n    res = SortedMerge(a, b);\r\n  \r\n    printf(&quot;Merged Linked List is: &#92;n&quot;);\r\n    printList(res);\r\n  \r\n    return 0;\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_5083_2\">\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;iostream&gt;\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\r\n\/* Using this function we will be printing the 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;&lt;&lt;endl;\r\n}\r\n\r\n\/* Using this function we will be merging the two given sorted linked lists into a single sorted linked list *\/\r\nNode *mergeTwoLists(Node *l1, Node *l2) {\r\n        Node dummy(INT_MIN);\r\n        Node *tail = &amp;dummy;\r\n        \r\n        while (l1 &amp;&amp; l2) {\r\n            if (l1-&gt;data &lt; l2-&gt;data) {\r\n                tail-&gt;next = l1;\r\n                l1 = l1-&gt;next;\r\n            } else {\r\n                tail-&gt;next = l2;\r\n                l2 = l2-&gt;next;\r\n            }\r\n            tail = tail-&gt;next;\r\n        }\r\n\r\n        tail-&gt;next = l1 ? l1 : l2;\r\n        return dummy.next;\r\n    }\r\n\r\n\r\n\/* Main function *\/\r\nint main()\r\n{\r\n    Node *list1 = new Node(2);\r\n    list1-&gt;next = new Node(3);\r\n    list1-&gt;next-&gt;next = new Node(5);\r\n    list1-&gt;next-&gt;next-&gt;next = new Node(9);\r\n\r\n    Node *list2 = new Node(1);\r\n    list2-&gt;next = new Node(4);\r\n    list2-&gt;next-&gt;next = new Node(8);\r\n    \r\n    cout&lt;&lt;&quot;Original linked list 1: &quot;&lt;&lt;endl;\r\n    print(list1);\r\n    cout&lt;&lt;&quot;Original linked list 2: &quot;&lt;&lt;endl;\r\n    print(list2);\r\n\r\n    Node* result = mergeTwoLists(list1,list2);\r\n    \r\n    cout&lt;&lt;&quot;Merged sorted linked list: &quot;&lt;&lt;endl;\r\n    print(result);\r\n\r\n    return 0;\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_5083_3\">\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\n\r\nclass Node\r\n{\r\n\tint data;\r\n\tNode next;\r\n\tNode(int d) {data = d;\r\n\t\t\t\tnext = null;}\r\n}\r\nclass Sort\r\n{\r\n    Node sortedMerge(Node headA, Node headB)\r\n    {\r\n\t    \/* a dummy first node to chang the result on *\/\r\n\t    Node dummyNode = new Node(0);\r\n\t    \/* tail points to the last result node *\/\r\n\t    Node tail = dummyNode;\r\n\t    while(true)\r\n\t    {\r\n\t\t    \/* if either list runs out,\r\n\t\t    use the other list *\/\r\n\t\t    if(headA == null)\r\n\t\t    {\r\n\t\t\t    tail.next = headB;\r\n\t\t\t    break;\r\n\t\t    }\r\n\t\t    if(headB == null)\r\n\t\t    {\r\n\t\t\t    tail.next = headA;\r\n\t\t\t    break;\r\n\t\t    }\r\n\t\t    \/* Compare the data of the two\r\n\t\t    lists whichever lists' data is\r\n\t\t    smaller, append it into tail and\r\n\t\t    advance the head to the next Node*\/\r\n\t\t    if(headA.data <= headB.data)\r\n\t\t    {\r\n\t\t\t    tail.next = headA;\r\n\t\t\t    headA = headA.next;\r\n\t\t    }\r\n\t\t    else\r\n\t\t    {\r\n\t\t\t    tail.next = headB;\r\n\t\t\t    headB = headB.next;\r\n\t\t    }\r\n\t\t    tail = tail.next;\r\n\t    }\r\n\t    return dummyNode.next;\r\n    }\r\n}\t\r\nclass Merge2Sorted\r\n{\r\n    Node head;\r\n    public void addToTheLast(Node node)\r\n    {\r\n\t    if (head == null)\r\n\t    {\r\n\t\t    head = node;\r\n\t    }\r\n\t    else\r\n\t    {\r\n\t\t    Node temp = head;\r\n\t\t    while (temp.next != null)\r\n\t\t\t    temp = temp.next;\r\n\t\t    temp.next = node;\r\n\t    }\r\n    }\r\n    void printList()\r\n    {\r\n    \tNode temp = head;\r\n\t    while (temp != null)\r\n\t    {\r\n\t\t    System.out.print(temp.data + \" \");\r\n\t\t    temp = temp.next;\r\n\t    }\r\n\t    System.out.println();\r\n    }\r\n    \/\/ Driver Code\r\n    public static void main(String args[])\r\n    {   \r\n\t\r\n\tMerge2Sorted llist1 = new Merge2Sorted();\r\n\tMerge2Sorted llist2 = new Merge2Sorted();\r\n\t\r\n\t\/\/ Node head1 = new Node(5);\r\n\tllist1.addToTheLast(new Node(5));\r\n\tllist1.addToTheLast(new Node(10));\r\n\tllist1.addToTheLast(new Node(15));\r\n\t\r\n\t\/\/ Node head2 = new Node(2);\r\n\tllist2.addToTheLast(new Node(2));\r\n\tllist2.addToTheLast(new Node(3));\r\n\tllist2.addToTheLast(new Node(20));\r\n\t\r\n\t\r\n\tllist1.head = new Sort().sortedMerge(llist1.head,\r\n\t\t\t\t\t\t\t\t\t\tllist2.head);\r\n\tllist1.printList();\t\r\n\t\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_5083_4\">\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\nclass Node:\r\n    def __init__(self, data):\r\n        self.data = data\r\n        self.next = None\r\n\r\nclass LinkedList:\r\n    def __init__(self):\r\n        self.head = None\r\n\r\n    def printList(self):\r\n        temp = self.head\r\n        while temp:\r\n            print(temp.data, end=\" \")\r\n            temp = temp.next\r\n\r\n    def addToList(self, newData):\r\n        newNode = Node(newData)\r\n        if self.head is None:\r\n            self.head = newNode\r\n            return\r\n\r\n        last = self.head\r\n        while last.next:\r\n            last = last.next\r\n\r\n        last.next = newNode\r\n\r\ndef mergeLists(headA, headB):\r\n\r\n    dummyNode = Node(0)\r\n\r\n    tail = dummyNode\r\n    while True:\r\n\r\n        if headA is None:\r\n            tail.next = headB\r\n            break\r\n        if headB is None:\r\n            tail.next = headA\r\n            break\r\n\r\n        if headA.data <= headB.data:\r\n            tail.next = headA\r\n            headA = headA.next\r\n        else:\r\n            tail.next = headB\r\n            headB = headB.next\r\n\r\n        tail = tail.next\r\n\r\n    return dummyNode.next\r\n\r\n\r\nlistA = LinkedList()\r\nlistB = LinkedList()\r\n\r\nlistA.addToList(2)\r\nlistA.addToList(3)\r\nlistA.addToList(5)\r\nlistA.addToList(9)\r\n\r\nlistB.addToList(1)\r\nlistB.addToList(4)\r\nlistB.addToList(8)\r\n\r\nprint(\"Original linked list 1:\")\r\nlistA.printList()\r\n\r\nprint(\"&#92;nOriginal linked list 2:\")\r\nlistB.printList()\r\nlistA.head = mergeLists(listA.head, listB.head)\r\n\r\nprint(\"&#92;nMerged Linked List is:\")\r\nlistA.printList()\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\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_5083 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_5083 a\"),jQuery(\"#tab-content_5083\"));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<h4>Output<\/h4>\n<p>Original linked list 1:<br \/>\n2 -&gt; 3 -&gt; 5 -&gt; 9 -&gt; NULL<br \/>\nOriginal linked list 2:<br \/>\n1 -&gt; 4 -&gt; 8 -&gt; NULL<br \/>\nMerged sorted linked list:<br \/>\n1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 8 -&gt; 9 -&gt; NULL<\/p>\n<p><strong>Time Complexity:<\/strong> O(n), where n is the total number of nodes in both the lists.<br \/>\n[forminator_quiz id=&#8221;5081&#8243;]<\/p>\n<p>So, in this blog, we have tried to explain how you can merge two sorted linked lists in the most optimal way. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Prepbytes (Linked List)<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews. Problem Statement In this problem, we will be given two sorted linked lists. We need to merge both lists such that [&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-5080","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 two sorted linked lists | Linked List | Prepbytes<\/title>\n<meta name=\"description\" content=\"Learn to merge two sorted linked lists.\" \/>\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-two-sorted-linked-lists\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Merge two sorted linked lists | Linked List | Prepbytes\" \/>\n<meta property=\"og:description\" content=\"Learn to merge two sorted linked lists.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/\" \/>\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-20T06:35:33+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-04-20T20:18:57+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.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=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Merge two sorted linked lists\",\"datePublished\":\"2021-09-20T06:35:33+00:00\",\"dateModified\":\"2022-04-20T20:18:57+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/\"},\"wordCount\":1096,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/\",\"name\":\"Merge two sorted linked lists | Linked List | Prepbytes\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png\",\"datePublished\":\"2021-09-20T06:35:33+00:00\",\"dateModified\":\"2022-04-20T20:18:57+00:00\",\"description\":\"Learn to merge two sorted linked lists.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#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 two sorted linked lists\"}]},{\"@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 two sorted linked lists | Linked List | Prepbytes","description":"Learn to merge two sorted linked lists.","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-two-sorted-linked-lists\/","og_locale":"en_US","og_type":"article","og_title":"Merge two sorted linked lists | Linked List | Prepbytes","og_description":"Learn to merge two sorted linked lists.","og_url":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-09-20T06:35:33+00:00","article_modified_time":"2022-04-20T20:18:57+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Merge two sorted linked lists","datePublished":"2021-09-20T06:35:33+00:00","dateModified":"2022-04-20T20:18:57+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/"},"wordCount":1096,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/","url":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/","name":"Merge two sorted linked lists | Linked List | Prepbytes","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png","datePublished":"2021-09-20T06:35:33+00:00","dateModified":"2022-04-20T20:18:57+00:00","description":"Learn to merge two sorted linked lists.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007306408-Article_153.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists\/#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 two sorted linked lists"}]},{"@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\/5080","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=5080"}],"version-history":[{"count":6,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5080\/revisions"}],"predecessor-version":[{"id":8004,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5080\/revisions\/8004"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=5080"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=5080"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=5080"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}