{"id":5225,"date":"2021-09-24T09:02:12","date_gmt":"2021-09-24T09:02:12","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5225"},"modified":"2022-11-22T06:57:05","modified_gmt":"2022-11-22T06:57:05","slug":"merge-two-sorted-linked-lists-in-place","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/","title":{"rendered":"Merge two sorted linked lists (in-place)"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png\" alt=\"\" \/><\/p>\n<p>In this article, we will learn how to merge two sorted linked lists. Sorting is defined as the technique of arranging the elements either in ascending or descending order. let\u2019s try to understand how we can approach merge 2 sorted linked list.<\/p>\n<h2>How to Merge 2 Sorted Linked List<\/h2>\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<p>The problem statement is quite straightforward, we will get 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><strong>Note:<\/strong> Remember that we cannot use any extra space, as we need to do this in place.<\/p>\n<p>Let&#8217;s try to understand how to merge two sorted linked lists more clearly using examples.<\/p>\n<p>Let the two sorted lists given to us be <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/inplace2-01.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 list should be:<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/output-22.png\" alt=\"\" \/><\/p>\n<p>Let\u2019s take another example:<br \/>\nLet the two sorted lists given to us be 2\u21928\u21929\u219210\u2192NULL and 11\u219213\u219217\u2192NULL<\/p>\n<ul>\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<p><strong>Some more examples of merge two sorted linked lists<\/strong><\/p>\n<p><strong>Sample Input 1: <\/strong><\/p>\n<ul>\n<li>list 1: 1\u21922\u21925\u219210\u2192NULL<\/li>\n<li>list 2: 3\u21927\u21929\u219211\u2192NULL<\/li>\n<\/ul>\n<p><strong>Sample Output 1:<\/strong> 1\u21922\u21923\u21925\u21927\u21929\u219210\u219211\u2192NULL<\/p>\n<p><strong>Sample Input 2:<\/strong><\/p>\n<ul>\n<li>list 1: 2\u21923\u21929\u219210\u2192NULL<\/li>\n<li>list 2: 4\u21925\u21927\u21928\u219212\u2192NULL<\/li>\n<\/ul>\n<p><strong>Sample Output 2:<\/strong> 2\u21923\u21924\u21925\u21927\u21928\u21929\u219210\u219212\u2192NULL<\/p>\n<p>At this point, we have understood the problem statement. Now we will try to formulate an approach to merge two sorted linked lists.<\/p>\n<ul>\n<li>Before moving to the approach section, try to think about how you can merge two sorted linked lists.<\/li>\n<\/ul>\n<p>If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.<\/p>\n<p>Let\u2019s move to the approach section to merge two sorted linked lists.<\/p>\n<h2>Approach 1 to merge 2 sorted linked list<\/h2>\n<p>Our approach will be simple:<\/p>\n<ul>\n<li>We will make a recursive function that will create a sorted list out of two given sorted lists.<\/li>\n<li>If both the heads of the linked lists are NULL, return NULL and if only one head is NULL, then return the other head.<\/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 call the recursive function again with parameters as the next node of the list having a smaller head value and the head of the other list.<\/li>\n<li>Our recursive call will be returning the next smaller element of the linked lists attached with the rest of the sorted list. Make the next of the current node point to the list returned by the recursive function <strong>(curr_node-&gt; next = recursive function())<\/strong>.<\/li>\n<\/ul>\n<p>Following all the above steps, we will have our merged sorted list containing nodes of all the given linked lists in sorted order.<\/p>\n<h2>Algorithm 1 to merge two sorted linked lists<\/h2>\n<p>1) The recursive function will have two parameters, i.e., <strong>head1<\/strong> and <strong>head2<\/strong>, denoting the current head node of the <strong>first<\/strong> and <strong>second list<\/strong>, respectively.<br \/>\n2) Base case: <\/p>\n<ul>\n<li>If both of the head nodes are NULL, return NULL from there.<\/li>\n<li>If one of the head nodes is NULL, but the other one is not NULL, return the other head.<br \/>\n3) If <strong>head1\u2019s data<\/strong> is less than <strong>head2\u2019s data<\/strong>, assign <strong>head1\u2019s next<\/strong> to the result returned by the recursive function having parameters <strong>head1\u2192next<\/strong> and <strong>head2<\/strong> and then return <strong>head1<\/strong>.<br \/>\n4) Else, assign <strong>head2\u2019s next<\/strong> to the result returned by the recursive function having parameters <strong>head1<\/strong> and <strong>head2\u2192next<\/strong> and then return <strong>head2<\/strong>.<\/li>\n<\/ul>\n<p><strong>Time Complexity:<\/strong> O(n), n is the number of nodes in both 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 memory? <\/p>\n<ul>\n<li>The answer is yes, and to know it, have a look at the helpful observations and also read the below approach which uses constant memory.<\/li>\n<\/ul>\n<h4>Helpful Observations to merge 2 sorted linked list<\/h4>\n<ul>\n<li>If we observe, we can see that we need two pointers at the beginning of both list since the smallest value will be present at the beginning of both lists.<\/li>\n<li>The list has a smaller first node that will be considered as the first list and the other one would be considered the second list.<\/li>\n<li>We then have to just insert the second pointer node between the first and its next node if its value lies between the first and its next node.<\/li>\n<li>If that is not the case, then we just need to move forward in iteration.<\/li>\n<\/ul>\n<p>Applying the above observations, we can easily create the new sorted linked list.<\/p>\n<h2>Approach 2 to merge two sorted linked lists<\/h2>\n<p>Taking help from the observation explained above, let us understand the approach to merge two sorted linked lists with the help of an example.<\/p>\n<ul>\n<li>Let the input lists be 1\u21924\u21927\u219210\u2192NULL and 2\u21923\u219222\u2192NULL<\/li>\n<li>We would keep two pointers &#8211; one at the start of each linked list.<\/li>\n<li>Now, the first pointer will point to \u20181\u2019 because the first list has a smaller first node, and the second one will point to \u20182\u2019 because it has a greater first node.<\/li>\n<li>Since the second pointer\u2019s data lies between \u20181\u2019 and \u20184\u2019 (first pointer\u2019s data and next of first pointer\u2019s data), so we insert it between \u20181\u2019 and \u20184\u2019.<\/li>\n<li>After inserting the second node, we update the head of the second list to its next node.<\/li>\n<li>Now let\u2019s suppose the value of the second pointer was greater than \u20184\u2019 so, we would not do anything in this case and just move our first pointer forward by one node.<\/li>\n<\/ul>\n<p>Now, let\u2019s formulate an algorithm based on the approach discussed above and handle the edge cases that might be present while implementing the code.<\/p>\n<h2>Algorithm 2 to merge two sorted linked lists<\/h2>\n<ul>\n<li>Find which list has a smaller first node and consider it as the first list and the other one as the second list (<strong>flist<\/strong> stands for <strong>first list<\/strong> and <strong>slist<\/strong> stands for <strong>second list<\/strong>).<\/li>\n<li>Now, initialize four pointers:\n<ul>\n<li>First will point to the head of the first list ( say <strong>flist_curr<\/strong> ).<\/li>\n<li>The second will point to the second node of the first list ( say <strong>flist_next<\/strong> ).<\/li>\n<li>The third will point to the head of the second list ( say <strong>slist_curr<\/strong> ).<\/li>\n<li>The Fourth will point to the second node of the second list ( say <strong>slist_next<\/strong> ).<\/li>\n<\/ul>\n<\/li>\n<li>While iterating through the lists, we need to check if <strong>slist_curr\u2019s value<\/strong> lies between <strong>flist_curr\u2019s value<\/strong> and <strong>flist_next\u2019s value<\/strong>.<br \/>\na) If its value lies in between, then we need to insert the <strong>slist_curr<\/strong> node in between <strong>flist_curr<\/strong> and <strong>flist_next<\/strong> and update <strong>flist_curr<\/strong> to <strong>slist_curr<\/strong> and <strong>slist_curr<\/strong> to <strong>slist_next<\/strong>.<br \/>\nb) Else, we will check if there are more nodes in the first list.<\/p>\n<ul>\n<li>If there are more nodes in the first list, then just move <strong>flist_curr<\/strong> and <strong>flist_next<\/strong> to their respective next nodes.<\/li>\n<li>If that is not the case, then the last node of the first node should point to the remaining nodes of the second list, and then finally, we will return the head of the first list.<\/li>\n<\/ul>\n<\/li>\n<li>After performing the above steps, we would get our new list that is sorted.<\/li>\n<\/ul>\n<p>### Dry Run to merge two sorted linked lists<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_1-24.png\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_2-24.png\" alt=\"\" \/><br \/>\n<img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/p_3-14.png\" alt=\"\" \/><\/p>\n<p>## Code Implementation to merge two sorted linked lists<\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_5226 {\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_5226 .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_5226 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_5226 .wpsm_nav-tabs > li.active > a, #tab_container_5226 .wpsm_nav-tabs > li.active > a:hover, #tab_container_5226 .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_5226 .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_5226 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_5226 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_5226 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_5226 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_5226 .wpsm_nav-tabs > li > a:hover , #tab_container_5226 .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_5226 .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_5226 .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_5226 .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_5226 .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_5226 .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_5226 .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_5226 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5226 .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_5226 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_5226 .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_5226 .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_5226\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_5226\">\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_5226_1\" aria-controls=\"tabs_desc_5226_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_5226_2\" aria-controls=\"tabs_desc_5226_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_5226_3\" aria-controls=\"tabs_desc_5226_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_5226_4\" aria-controls=\"tabs_desc_5226_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_5226\">\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_5226_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;stdbool.h&gt;\r\n#include&lt;stdlib.h&gt;\r\n \r\nstruct Node {\r\n    int data;\r\n    struct Node* prev;\r\n    struct Node* next;\r\n};\r\n\r\nvoid push(struct Node **head_ref, int data)\r\n{\r\n    struct Node* ptr1 =\r\n            (struct Node*) malloc(sizeof(struct Node));\r\n    struct Node *temp = *head_ref;\r\n    ptr1-&gt;data = data;\r\n    ptr1-&gt;next = *head_ref;\r\n    if (*head_ref != NULL)\r\n    {\r\n        while (temp-&gt;next != *head_ref)\r\n            temp = temp-&gt;next;\r\n        temp-&gt;next = ptr1;\r\n    }\r\n    else\r\n        ptr1-&gt;next = ptr1; \r\n \r\n    *head_ref = ptr1;\r\n}\r\n\r\nvoid printList(struct Node *head)\r\n{\r\n    struct Node *temp = head;\r\n    if (head != NULL)\r\n    {\r\n        do\r\n        {\r\n            printf(&quot;%d &quot;,temp-&gt;data);\r\n            temp = temp-&gt;next;\r\n        }\r\n        while (temp != head);\r\n    }\r\n}\r\n\r\nint main(void)\r\n{\r\n    struct Node *head = NULL;\r\n    push(&amp;head, 15);\r\n    push(&amp;head, 18);\r\n    push(&amp;head, 7);\r\n    push(&amp;head, 1);\r\n \r\n    printf( &quot;Contents of Circular Linked List&#92;n &quot;);\r\n    printList(head);\r\n}\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_5226_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;bits\/stdc++.h&gt;\r\nusing namespace std;\r\nclass Node\r\n{\r\n    public:\r\n    int data;\r\n    Node* next;\r\n    Node(int x){\r\n        data = x;\r\n   next = NULL;\r\n    }\r\n};\r\n\r\n\r\nvoid printList(Node *head)\r\n{\r\n    if (!head)\r\n        return;\r\n     \r\n    while (head-&gt;next != NULL)\r\n    {\r\n        cout &lt;&lt; head-&gt;data &lt;&lt; &quot; -&gt; &quot;;\r\n        head = head-&gt;next;\r\n    }\r\n    cout &lt;&lt; head-&gt;data &lt;&lt; endl;\r\n}\r\n \r\nNode* mergeTwoSortedLists(Node* head1, Node* head2)\r\n{\r\n    \/\/ if first list has only one node\r\n    if (!head1-&gt;next) {\r\n        head1-&gt;next = head2;\r\n        return head1;\r\n    }\r\n    \/\/ make the list with smaller first node as first list\r\n    if((head1-&gt;data) &gt; (head2-&gt;data)){\r\n        Node *temp = head1;\r\n        head1 = head2;\r\n       head2 = temp;\r\n    }\r\n    \/\/ Initialize all four pointer as discussed above in step 1 \r\n    Node *flist_curr = head1, *flist_next = head1-&gt;next;\r\n    Node *slist_curr = head2, *slist_next = head2-&gt;next;\r\n \r\n    while (flist_next &amp;&amp; slist_curr) {\r\n        \/\/ if value of slist_curr lies in between value of flist_curr and\r\n        \/\/ value of flist_next then insert slist_curr between flist_curr and \r\n        \/\/ flist_next\r\n        if ((slist_curr-&gt;data) &gt;= (flist_curr-&gt;data) &amp;&amp; (slist_curr-&gt;data) &lt;= (flist_next-&gt;data)) {\r\n            slist_next = slist_curr-&gt;next;\r\n            flist_curr-&gt;next = slist_curr;\r\n            slist_curr-&gt;next = flist_next;\r\n \r\n            \/\/ update flist_curr to point to slist_curr and slist_curr to point to slist_next\r\n            flist_curr = slist_curr;\r\n            slist_curr = slist_next;\r\n        }\r\n        else {\r\n            \/\/ if we have not reached end of first list\r\n            if (flist_next-&gt;next) {\r\n                flist_next = flist_next-&gt;next;\r\n                flist_curr = flist_curr-&gt;next;\r\n            }\r\n \r\n            \/\/ if we have reached the end of the first list then \r\n            \/\/ point last node&rsquo;s next to remaining nodes of \r\n            \/\/ second list\r\n            else {\r\n                flist_next-&gt;next = slist_curr;\r\n                return head1;\r\n            }\r\n        }\r\n    }\r\n    return head1;\r\n}\r\n \r\nint main(void)\r\n{\r\n    Node* head1 = NULL;\r\n    head1 = new Node(1);\r\n    head1-&gt;next = new Node(4);\r\n    head1-&gt;next-&gt;next = new Node(7);\r\n    head1-&gt;next-&gt;next-&gt;next = new Node(10);\r\n \r\n    Node* head2 = NULL;\r\n    head2 = new Node(2);\r\n    head2-&gt;next = new Node(3);\r\n    head2-&gt;next-&gt;next = new Node(22);\r\n \r\n    Node *tmp = mergeTwoSortedLists(head1,head2);\r\n    cout&lt;&lt;&quot;Merged Linked list&quot;&lt;&lt;endl;\r\n    printList(tmp);\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_5226_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\nclass MergeInPlace {\r\n\r\n    static class Node {\r\n        int data;\r\n        Node next;\r\n    }\r\n    static Node newNode(int key)\r\n    {\r\n        Node temp = new Node();\r\n        temp.data = key;\r\n        temp.next = null;\r\n        return temp;\r\n    }\r\n    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\r\n    \/\/ Merges two lists with headers as h1 and h2.\r\n    \/\/ It assumes that h1's data is smaller than\r\n    \/\/ or equal to h2's data.\r\n    static Node mergeUtil(Node h1, Node h2)\r\n    {\r\n        \/\/ if only one node in first list\r\n        \/\/ simply point its head to second list\r\n        if (h1.next == null) {\r\n            h1.next = h2;\r\n            return h1;\r\n        }\r\n        \/\/ Initialize current and next pointers of\r\n        \/\/ both lists\r\n        Node curr1 = h1, next1 = h1.next;\r\n        Node curr2 = h2, next2 = h2.next;\r\n\r\n        while (next1 != null &amp;&amp; curr2 != null) {\r\n            \/\/ if curr2 lies in between curr1 and next1\r\n            \/\/ then do curr1-&gt;curr2-&gt;next1\r\n            if ((curr2.data) &gt;= (curr1.data) &amp;&amp; (curr2.data) &lt;= (next1.data)) {\r\n                next2 = curr2.next;\r\n                curr1.next = curr2;\r\n                curr2.next = next1;\r\n\r\n                \/\/ now let curr1 and curr2 to point\r\n                \/\/ to their immediate next pointers\r\n                curr1 = curr2;\r\n                curr2 = next2;\r\n            }\r\n            else {\r\n                \/\/ if more nodes in first list\r\n                if (next1.next != null) {\r\n                    next1 = next1.next;\r\n                    curr1 = curr1.next;\r\n                }\r\n\r\n                \/\/ else point the last node of first list\r\n                \/\/ to the remaining nodes of second list\r\n                else {\r\n                    next1.next = curr2;\r\n                    return h1;\r\n                }\r\n            }\r\n        }\r\n        return h1;\r\n    }\r\n    \/\/ Merges two given lists in-place. This function\r\n    \/\/ mainly compares head nodes and calls mergeUtil()\r\n    static Node merge(Node h1, Node h2)\r\n    {\r\n        if (h1 == null)\r\n            return h2;\r\n        if (h2 == null)\r\n            return h1;\r\n\r\n        \/\/ start with the linked list\r\n        \/\/ whose head data is the least\r\n        if (h1.data &lt; h2.data)\r\n            return mergeUtil(h1, h2);\r\n        else\r\n            return mergeUtil(h2, h1);\r\n    }\r\n    \/\/ Driver code\r\n    public static void main(String[] args)\r\n    {\r\n        Node head1 = newNode(1);\r\n        head1.next = newNode(3);\r\n        head1.next.next = newNode(5);\r\n\r\n        \/\/ 1-&gt;3-&gt;5 LinkedList created\r\n\r\n        Node head2 = newNode(0);\r\n        head2.next = newNode(2);\r\n        head2.next.next = newNode(4);\r\n\r\n        \/\/ 0-&gt;2-&gt;4 LinkedList created\r\n\r\n        Node mergedhead = merge(head1, head2);\r\n\r\n        printList(mergedhead);\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_5226_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\ndef newNode(key):\r\n\r\n    temp = Node(0)\r\n    temp.data = key\r\n    temp.next = None\r\n    return temp\r\n\r\ndef printList(node):\r\n\r\n    while (node != None) :\r\n        print( node.data, end =&quot; &quot;)\r\n        node = node.next\r\n    \r\ndef mergeUtil(h1, h2):\r\n\r\n    if (h1.next == None) :\r\n        h1.next = h2\r\n        return h1\r\n    \r\n    curr1 = h1\r\n    next1 = h1.next\r\n    curr2 = h2\r\n    next2 = h2.next\r\n\r\n    while (next1 != None and curr2 != None):\r\n    \r\n        if ((curr2.data) &gt;= (curr1.data) and\r\n            (curr2.data) &lt;= (next1.data)) :\r\n            next2 = curr2.next\r\n            curr1.next = curr2\r\n            curr2.next = next1\r\n\r\n            curr1 = curr2\r\n            curr2 = next2\r\n        \r\n        else :\r\n            if (next1.next) :\r\n                next1 = next1.next\r\n                curr1 = curr1.next\r\n            \r\n            else :\r\n                next1.next = curr2\r\n                return h1\r\n\r\n    return h1\r\n\r\ndef merge( h1, h2):\r\n\r\n    if (h1 == None):\r\n        return h2\r\n    if (h2 == None):\r\n        return h1\r\n\r\n    if (h1.data &lt; h2.data):\r\n        return mergeUtil(h1, h2)\r\n    else:\r\n        return mergeUtil(h2, h1)\r\n\r\n\r\nhead1 = newNode(1)\r\nhead1.next = newNode(4)\r\nhead1.next.next = newNode(7)\r\nhead1.next.next.next = newNode(10)\r\n\r\n\r\nhead2 = newNode(2)\r\nhead2.next = newNode(3)\r\nhead2.next.next = newNode(22)\r\n\r\n\r\nmergedhead = merge(head1, head2)\r\n\r\nprint(&quot;Merged Linked list&quot;)\r\nprintList(mergedhead)\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_5226 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_5226 a\"),jQuery(\"#tab-content_5226\"));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<p>    Output<br \/>\n    Merged Linked list<br \/>\n    1 -> 2 -> 3 -> 4 -> 7 -> 10 -> 22<\/p>\n<p>**Time Complexity:** O(n), where n is the number of nodes in the list.<\/p>\n<p>So, in this blog, we have tried to explain how to merge two sorted linked lists. We have explained various approaches with picturised dry runs and code implementation in various languages as well and also explained the optimization of space complexity. To brush up your skills on Linked List, which is you can follow this link <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>which is curated by our expert mentors at PrepBytes.<\/p>\n<p>## FAQs related to merge two sorted linked lists<\/p>\n<p>**1. How many comparisons would be required to merge two sorted lists?**<br \/>\nTo merge two lists of sizes m and n, we need to do m+n-1 comparisons in the worst case.<\/p>\n<p>**2. Why is merge sort important?**<br \/>\nWith merge sort, we can efficiently sort a list in O(n*log(n)) time complexity.<\/p>\n<p>**3. What type of approach is used in merge sort ?**<br \/>\nMerge sort is a sorting technique based on the divide and conquer technique. Having worst-case time complexity being \u039f(n* log(n)), it is one of the most respected algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this article, we will learn how to merge two sorted linked lists. Sorting is defined as the technique of arranging the elements either in ascending or descending order. let\u2019s try to understand how we can approach merge 2 sorted linked list. How to Merge 2 Sorted Linked List In this problem, we will be [&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-5225","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 (in-place) | Linked list articles | PrepBytes Blog<\/title>\n<meta name=\"description\" content=\"Learn how to merge two sorted linked lists (in-place) in the most optimal way.\" \/>\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-in-place\/\" \/>\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 (in-place) | Linked list articles | PrepBytes Blog\" \/>\n<meta property=\"og:description\" content=\"Learn how to merge two sorted linked lists (in-place) in the most optimal way.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/\" \/>\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-24T09:02:12+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-11-22T06:57:05+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.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=\"7 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-in-place\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Merge two sorted linked lists (in-place)\",\"datePublished\":\"2021-09-24T09:02:12+00:00\",\"dateModified\":\"2022-11-22T06:57:05+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/\"},\"wordCount\":1445,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/\",\"name\":\"Merge two sorted linked lists (in-place) | Linked list articles | PrepBytes Blog\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png\",\"datePublished\":\"2021-09-24T09:02:12+00:00\",\"dateModified\":\"2022-11-22T06:57:05+00:00\",\"description\":\"Learn how to merge two sorted linked lists (in-place) in the most optimal way.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#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 (in-place)\"}]},{\"@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 (in-place) | Linked list articles | PrepBytes Blog","description":"Learn how to merge two sorted linked lists (in-place) in the most optimal way.","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-in-place\/","og_locale":"en_US","og_type":"article","og_title":"Merge two sorted linked lists (in-place) | Linked list articles | PrepBytes Blog","og_description":"Learn how to merge two sorted linked lists (in-place) in the most optimal way.","og_url":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-09-24T09:02:12+00:00","article_modified_time":"2022-11-22T06:57:05+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"7 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Merge two sorted linked lists (in-place)","datePublished":"2021-09-24T09:02:12+00:00","dateModified":"2022-11-22T06:57:05+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/"},"wordCount":1445,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/","url":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/","name":"Merge two sorted linked lists (in-place) | Linked list articles | PrepBytes Blog","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png","datePublished":"2021-09-24T09:02:12+00:00","dateModified":"2022-11-22T06:57:05+00:00","description":"Learn how to merge two sorted linked lists (in-place) in the most optimal way.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007491098-Article_160.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/merge-two-sorted-linked-lists-in-place\/#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 (in-place)"}]},{"@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\/5225","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=5225"}],"version-history":[{"count":6,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5225\/revisions"}],"predecessor-version":[{"id":10676,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/5225\/revisions\/10676"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=5225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=5225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=5225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}