{"id":4906,"date":"2021-09-14T11:27:21","date_gmt":"2021-09-14T11:27:21","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4906"},"modified":"2022-11-22T06:10:34","modified_gmt":"2022-11-22T06:10:34","slug":"clone-a-linked-list-with-next-and-random-pointer-in-o1-space","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/","title":{"rendered":"Clone a linked list with next and random pointer in O(1) space"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png\" alt=\"\" \/><\/p>\n<p>In this article, we will learn to clone a linked list with next and random pointer.Cloning is defined copying the linked list without changing its structure and data. so let\u2019s try to understand how to clone a linked list with next and random pointer. <\/p>\n<h2>How to Clone a Linked List with Next and Random Pointer<\/h2>\n<p>In this problem, we are given a linked list of length N having two pointers in each node. The first pointer points to the next node of the list, and the second one is a random pointer which can point to any node of the linked list or NULL. Now we are asked to write a program that clones the given list in O(1) space.<\/p>\n<p><strong>Note:<\/strong> The cloned linked list should consist of exactly N new nodes, where the value of each node is the same as the corresponding value in the original linked list and the next and random pointers of the new nodes should point to new nodes in the cloned linked list in such a way that the pointers in the original linked list and cloned linked state represent the same list state. Finally, you have to return the head of the cloned linked list.<\/p>\n<p>First, we need to understand what cloning a linked list means.<\/p>\n<ul>\n<li>Cloning means copying the linked list without changing its structure and data. The addresses of the nodes will change as new nodes will be created for the cloned list.<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/understanding.png\" alt=\"\" \/><\/p>\n<p><\/p>\n<p>From the above figure, we can see that the addresses of the cloned nodes are different, but the structure and data of the linked list are the same.<\/p>\n<ul>\n<li>So basically, first, we have to clone a linked list and then return the head of the cloned linked list as output.<\/li>\n<\/ul>\n<h5>Example<\/h5>\n<p><strong>Input linked list<\/strong><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/example.png\" alt=\"\" \/><\/p>\n<p><strong>Output: A new linked list that is a copy of the original list<\/strong><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/example.png\" alt=\"\" \/><\/p>\n<p>Now I think from the above examples, the problem statement is clear. So let&#8217;s see how we will approach to clone a linked list with next and random pointer. Any Ideas?<\/p>\n<ul>\n<li>If not, it&#8217;s okay. We will see in the next section thoroughly how we can approach to clone a linked list with next and random pointer.<\/li>\n<\/ul>\n<p>Let\u2019s move to the next section.<\/p>\n<h2>Approach to clone a linked list with next and random pointer<\/h2>\n<p>Our approach will be simple:<\/p>\n<ul>\n<li>We will make a copy of the given linked list so that the next pointer of every node will simply point to the copy of the next node.<\/li>\n<li>But for the random pointer, we will find out which node number it is pointing at in the original linked list.\n<ul>\n<li>For example, in the original linked list the random pointer of 1<sup>st<\/sup> node is pointing to the 3<sup>rd<\/sup> node so we can see that in the cloned list also the random pointer of the first node is pointing to the third node.<\/li>\n<li>For doing this in the O(n) time complexity. We will use a clever technique. What we will do is we will make a copy of the node and put it between the node and node-&gt; next. In this way, we will observe that we can do the assignment of random pointers in O(1) time for every n node.<\/li>\n<\/ul>\n<\/li>\n<li>Finally, after random pointer linking, we will separate the cloned list from the sequence of original and copied nodes and output the cloned linked list.<\/li>\n<\/ul>\n<p>Let&#8217;s move to the algorithm section to see the above approach to clone a linked list with next and random pointer step by step in detail.<\/p>\n<p>## Algorithm to clone a linked list with next and random pointer<\/p>\n<ul>\n<li>We will first create a copy of 1<sup>st<\/sup> node and insert it between 1<sup>st<\/sup> node and 2<sup>nd<\/sup> in the original linked list. <\/li>\n<li>Similarly, we will create a copy of 2<sup>nd<\/sup> and will insert it between 2<sup>nd<\/sup> and 3<sup>rd<\/sup> node. We will continue in this manner and add the copy of node X<sup>th<\/sup> between X<sup>th<\/sup> node and (X+1)<sup>th<\/sup> node. The example given below will help you to understand this step better.\n<ul>\n<li>If A -&gt; B -&gt; C is our original linked list, then the linked list after the above steps of adding a copy of X<sup>th<\/sup> between X<sup>th<\/sup> and (X+1)<sup>th<\/sup> node will be A -&gt; A\u2019 -&gt; B -&gt; B\u2019 -&gt; C -&gt; C\u2019.<\/li>\n<\/ul>\n<\/li>\n<li>Now we will link the random pointers of the newly created nodes in the following manner:\n<ul>\n<li><strong>original-&gt;next-&gt;random = original-&gt;random-&gt;next<\/strong>.<\/li>\n<li>Why does this work? This works because <strong>original-&gt; next<\/strong> is simply a copy of the original and <strong>original-&gt;random-&gt; next<\/strong> is simply a copy of the random.<\/li>\n<\/ul>\n<\/li>\n<li>Now we will restore the original and cloned linked lists in a below manner by using a single loop.\n<ul>\n<li><strong>original-&gt;next = original-&gt;next-&gt;next<\/strong><\/li>\n<li><strong>copy-&gt;next = copy-&gt;next-&gt;next<\/strong><\/li>\n<\/ul>\n<\/li>\n<li>Taking the previous example only, A -&gt; B -&gt; C is the original list and the cloned list will be A\u2019 -&gt; B\u2019 -&gt; C\u2019.<\/li>\n<li>Make sure that <strong>original-&gt; next<\/strong> is NULL and finally return the head of the cloned list.<\/li>\n<\/ul>\n<p>### Dry Run to clone a linked list with next and random pointer<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-1.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-2.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-3.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-4.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-5.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-6.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-7.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Clone-a-linked-list-with-next-and-random-pointer-in-O1-space-8.png\" alt=\"\" \/><\/p>\n<p>## Code Implementation<\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_4908 {\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_4908 .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_4908 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_4908 .wpsm_nav-tabs > li.active > a, #tab_container_4908 .wpsm_nav-tabs > li.active > a:hover, #tab_container_4908 .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_4908 .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_4908 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_4908 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_4908 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_4908 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_4908 .wpsm_nav-tabs > li > a:hover , #tab_container_4908 .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_4908 .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_4908 .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_4908 .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_4908 .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_4908 .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_4908 .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_4908 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4908 .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_4908 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4908 .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_4908 .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_4908\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_4908\">\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_4908_1\" aria-controls=\"tabs_desc_4908_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_4908_2\" aria-controls=\"tabs_desc_4908_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_4908_3\" aria-controls=\"tabs_desc_4908_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_4908_4\" aria-controls=\"tabs_desc_4908_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_4908\">\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_4908_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\r\nstruct Node\r\n{\r\n    int data;\r\n    struct Node *next;\r\n    struct Node *random;\r\n    \r\n};\r\n\r\nstruct Node *newNode(int x)\r\n{\r\n    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));\r\n    temp-&gt;data = x;\r\n    temp-&gt;next = NULL;\r\n    return temp;\r\n}\r\n \r\n\/\/ Utility function to print the list.\r\nvoid print(struct Node *start)\r\n{\r\n    struct Node *ptr = start;\r\n    while (ptr)\r\n    {\r\n        printf(&quot; Data = %d&quot;,ptr-&gt;data);\r\n        printf(&quot; , Random  = %d&#92;n&quot;,ptr-&gt;random-&gt;data);\r\n        \/\/printf(&quot;&#92;n&quot;);\r\n        ptr = ptr-&gt;next;\r\n    }\r\n}\r\n \r\n\/\/ This function clones a given linked list\r\n\/\/ in O(1) space\r\nstruct Node* clone(struct Node *start)\r\n{\r\n   struct Node* curr = start;\r\n   struct Node *temp;\r\n \r\n    \/\/ insert additional node after\r\n    \/\/ every node of original list\r\n    while (curr)\r\n    {\r\n        temp = curr-&gt;next;\r\n \r\n        \/\/ Inserting node\r\n        \/\/struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));\r\n        curr-&gt;next = newNode(curr-&gt;data);\r\n        curr-&gt;next-&gt;next = temp;\r\n        curr = temp;\r\n    }\r\n \r\n    curr = start;\r\n \r\n    \/\/ adjust the random pointers of the\r\n    \/\/ newly added nodes\r\n    while (curr)\r\n    {\r\n        if(curr-&gt;next)\r\n            curr-&gt;next-&gt;random = curr-&gt;random ?\r\n                                 curr-&gt;random-&gt;next : curr-&gt;random;\r\n \r\n        \/\/ move to the next newly added node by\r\n        \/\/ skipping an original node\r\n        curr = curr-&gt;next?curr-&gt;next-&gt;next:curr-&gt;next;\r\n    }\r\n \r\n    struct Node* original = start;\r\n    struct Node* copy = start-&gt;next;\r\n \r\n    \/\/ save the start of copied linked list\r\n    temp = copy;\r\n \r\n    \/\/ now separate the original list and copied list\r\n    while (original &amp;&amp; copy)\r\n    {\r\n        original-&gt;next =\r\n         original-&gt;next? original-&gt;next-&gt;next : original-&gt;next;\r\n \r\n        copy-&gt;next = copy-&gt;next?copy-&gt;next-&gt;next:copy-&gt;next;\r\n        original = original-&gt;next;\r\n        copy = copy-&gt;next;\r\n    }\r\n \r\n    return temp;\r\n}\r\n \r\n\/\/ Driver code\r\nint main()\r\n{\r\n    struct Node* start = newNode(1);\r\n    start-&gt;next = newNode(2);\r\n    start-&gt;next-&gt;next = newNode(3);\r\n    start-&gt;next-&gt;next-&gt;next = newNode(4);\r\n    start-&gt;next-&gt;next-&gt;next-&gt;next = newNode(5);\r\n \r\n    \/\/ 1's random points to 3\r\n    start-&gt;random = start-&gt;next-&gt;next;\r\n \r\n    \/\/ 2's random points to 1\r\n    start-&gt;next-&gt;random = start;\r\n \r\n    \/\/ 3's and 4's random points to 5\r\n    start-&gt;next-&gt;next-&gt;random =\r\n                    start-&gt;next-&gt;next-&gt;next-&gt;next;\r\n    start-&gt;next-&gt;next-&gt;next-&gt;random =\r\n                    start-&gt;next-&gt;next-&gt;next-&gt;next;\r\n \r\n    \/\/ 5's random points to 2\r\n    start-&gt;next-&gt;next-&gt;next-&gt;next-&gt;random =\r\n                                      start-&gt;next;\r\n \r\n    printf( &quot;Original list : &#92;n&quot;);\r\n    print(start);\r\n\r\n    printf( &quot;&#92;nCloned list : &#92;n&quot;);\r\n    struct Node *cloned_list = clone(start);\r\n    print(cloned_list);\r\n \r\n    return 0;\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_4908_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\n \r\n\/* Structure of a node *\/\r\nstruct Node\r\n{\r\n    int data;\r\n    Node *next,*random;\r\n    Node(int a)\r\n    {\r\n        data = a;\r\n        next = NULL;\r\n      random = NULL;\r\n    }\r\n};\r\n\r\n\/* This function is used to print the linked list *\/\r\nvoid printingLinkedList(Node *head)\r\n{\r\n    Node *ptr = head;\r\n    while (ptr != NULL)\r\n    {\r\n        cout &lt;&lt; &quot;Data = &quot; &lt;&lt; ptr-&gt;data &lt;&lt; &quot;, Random  = &quot; &lt;&lt; ptr-&gt;random-&gt;data &lt;&lt; endl;\r\n        ptr = ptr-&gt;next;\r\n    }\r\n}\r\n\r\n\/* This function will return the cloned linked list *\/\r\nNode* cloningLinkedList(Node *head)\r\n{\r\n    Node* curr = head, *temp;\r\n    while (curr != NULL)\r\n    {\r\n        temp = curr-&gt;next;\r\n        curr-&gt;next = new Node(curr-&gt;data);\r\n        curr-&gt;next-&gt;next = temp;\r\n        curr = temp;\r\n    }\r\n    curr = head;\r\n \r\n    while (curr != NULL)\r\n    {\r\n        if(curr-&gt;next)\r\n            curr-&gt;next-&gt;random = curr-&gt;random ?\r\n                                 curr-&gt;random-&gt;next : curr-&gt;random;\r\n        curr = curr-&gt;next?curr-&gt;next-&gt;next:curr-&gt;next;\r\n    }\r\n \r\n    Node* original = head, *copy = head-&gt;next;\r\n    temp = copy;\r\n \r\n    while ((original !=NULL) &amp;&amp; (copy != NULL))\r\n    {\r\n        original-&gt;next = original-&gt;next? original-&gt;next-&gt;next : original-&gt;next;\r\n        copy-&gt;next = copy-&gt;next?copy-&gt;next-&gt;next:copy-&gt;next;\r\n        original = original-&gt;next;\r\n        copy = copy-&gt;next;\r\n    }\r\n    return temp;\r\n}\r\n\r\nint main()\r\n{\r\n    Node* head = new Node(1);\r\n    head-&gt;next = new Node(3);\r\n    head-&gt;next-&gt;next = new Node(5);\r\n    head-&gt;next-&gt;next-&gt;next = new Node(7);\r\n \r\n    head-&gt;random = head-&gt;next-&gt;next;\r\n    head-&gt;next-&gt;random = head-&gt;next-&gt;next-&gt;next;\r\n    head-&gt;next-&gt;next-&gt;random = head-&gt;next;\r\n    head-&gt;next-&gt;next-&gt;next-&gt;random = head;\r\n                                       \r\n    cout &lt;&lt; &quot;Original linked list : &#92;n&quot;;\r\n    printingLinkedList(head);\r\n    cout &lt;&lt; &quot;&#92;nCloned linked list : &#92;n&quot;;\r\n    Node *clone = cloningLinkedList(head);\r\n    printingLinkedList(clone);\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_4908_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 Clone {\r\n \r\n    \/\/ Structure of linked list Node\r\n    static class Node {\r\n        int data;\r\n        Node next, random;\r\n        Node(int x)\r\n        {\r\n            data = x;\r\n            next = random = null;\r\n        }\r\n    }\r\n \r\n    \/\/ Utility function to print the list.\r\n    static void print(Node start)\r\n    {\r\n        Node ptr = start;\r\n        while (ptr != null) {\r\n            System.out.println(&quot;Data = &quot; + ptr.data\r\n                               + &quot;, Random = &quot;\r\n                               + ptr.random.data);\r\n            ptr = ptr.next;\r\n        }\r\n    }\r\n \r\n    \/\/ This function clones a given\r\n    \/\/ linked list in O(1) space\r\n    static Node clone(Node start)\r\n    {\r\n        Node curr = start, temp = null;\r\n        while (curr != null) {\r\n            temp = curr.next;\r\n            curr.next = new Node(curr.data);\r\n            curr.next.next = temp;\r\n            curr = temp;\r\n        }\r\n        curr = start;\r\n        while (curr != null) {\r\n            if (curr.next != null)\r\n            {\r\n                curr.next.random = (curr.random != null)? curr.random.next: curr.random;\r\n            }\r\n            curr = curr.next.next;                   \r\n        }\r\n \r\n        Node original = start, copy = start.next;\r\n        temp = copy;\r\n        while (original != null) {\r\n            original.next =original.next.next;\r\n \r\n          copy.next = (copy.next != null) ? copy.next.next\r\n                                            : copy.next;\r\n            original = original.next;\r\n            copy = copy.next;\r\n        }\r\n        return temp;\r\n    }\r\n \r\n    \/\/ Driver code\r\n    public static void main(String[] args)\r\n    {\r\n        Node start = new Node(1);\r\n        start.next = new Node(2);\r\n        start.next.next = new Node(3);\r\n        start.next.next.next = new Node(4);\r\n        start.next.next.next.next = new Node(5);\r\n \r\n        start.random = start.next.next;\r\n        start.next.random = start;\r\n \r\n        start.next.next.random = start.next.next.next.next;\r\n        start.next.next.next.random\r\n            = start.next.next.next.next;\r\n \r\n        start.next.next.next.next.random = start.next;\r\n \r\n        System.out.println(&quot;Original list : &quot;);\r\n        print(start);\r\n \r\n        System.out.println(&quot;Cloned list : &quot;);\r\n        Node cloned_list = clone(start);\r\n        print(cloned_list);\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_4908_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\n'''Structure of linked list node'''\r\nclass Node:\r\n\tdef __init__(self, data):\r\n\t\tself.data = data\r\n\t\tself.next = None\r\n\t\tself.random = None\r\n\r\n# This function will return the cloned linked list\r\ndef cloningLinkedList(original_root):\r\n\tcurr = original_root\r\n\twhile curr != None:\r\n\t\tnew = Node(curr.data)\r\n\t\tnew.next = curr.next\r\n\t\tcurr.next = new\r\n\t\tcurr = curr.next.next\r\n\r\n\tcurr = original_root\r\n\twhile curr != None:\r\n\t\tcurr.next.random = curr.random.next\r\n\t\tcurr = curr.next.next\r\n\r\n\tcurr = original_root\r\n\tdup_root = original_root.next\r\n\twhile curr.next != None:\r\n\t\ttmp = curr.next\r\n\t\tcurr.next = curr.next.next\r\n\t\tcurr = tmp\r\n\r\n\treturn dup_root\r\n\r\n# This function is used to print the linked list \r\ndef printingLinkedList(root):\r\n\r\n\tcurr = root\r\n\twhile curr != None:\r\n\t\tprint('Data =', curr.data, ', Random =', curr.random.data)\r\n\t\tcurr = curr.next\r\n\r\n\r\nhead = Node(1)\r\nhead.next = Node(3)\r\nhead.next.next = Node(5)\r\nhead.next.next.next = Node(7)\r\n\r\nhead.random = head.next.next\r\nhead.next.random = head.next.next.next\r\nhead.next.next.random = head.next\r\nhead.next.next.next.random = head\r\n\r\nprint('Original list:')\r\nprintingLinkedList(head)\r\ncloningLinkedListd_list = cloningLinkedList(head)\r\nprint('&#92;ncloningLinkedListd list:')\r\nprintingLinkedList(cloningLinkedListd_list)\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_4908 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_4908 a\"),jQuery(\"#tab-content_4908\"));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    Original linked list :<br \/>\n    Data = 1, Random  = 5<br \/>\n    Data = 3, Random  = 7<br \/>\n    Data = 5, Random  = 3<br \/>\n    Data = 7, Random  = 1<\/p>\n<p>    Cloned linked list :<br \/>\n    Data = 1, Random  = 5<br \/>\n    Data = 3, Random  = 7<br \/>\n    Data = 5, Random  = 3<br \/>\n    Data = 7, Random  = 1<\/p>\n<p><strong>Time Complexity:<\/strong> O(N), since we are only traversing over the length of the linked list.<\/p>\n<p>In this article, we have explained the most efficient approach to clone a linked list with next and random pointer. We discussed the solution with a complete dry run and code implementation in various languages with optimized time and space complexities. If you want to solve more questions on Linked List, visit <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>which are curated by our expert mentors at PrepBytes.<\/p>\n<p>## FAQs to clone a linked list with next and random pointer<\/p>\n<p>**1. What is the main advantage of a linked list?**<br \/>\nA linked list can be easily inserted or removed with reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory.<\/p>\n<p>**2. Which algorithm is not suitable for the linked list?**<br \/>\nA binary search algorithm is not suitable for a linked list.<\/p>\n<p>**3. How many types of linked list exists?**<br \/>\nThree types of a linked lists are there:<br \/>\n&#8211; Singly linked list<br \/>\n&#8211; Doubly linked list<br \/>\n&#8211; Circular linked list<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this article, we will learn to clone a linked list with next and random pointer.Cloning is defined copying the linked list without changing its structure and data. so let\u2019s try to understand how to clone a linked list with next and random pointer. How to Clone a Linked List with Next and Random Pointer [&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-4906","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>Clone a linked list with next and random pointer in O(1) space | Linked List | Prepbytes<\/title>\n<meta name=\"description\" content=\"Learn the most efficient way to clone a linked list with next and random pointer. This blog explains the most efficient approach to rearrange a given linked list in place.\" \/>\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\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Clone a linked list with next and random pointer in O(1) space | Linked List | Prepbytes\" \/>\n<meta property=\"og:description\" content=\"Learn the most efficient way to clone a linked list with next and random pointer. This blog explains the most efficient approach to rearrange a given linked list in place.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/\" \/>\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-14T11:27:21+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-11-22T06:10:34+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.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\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Clone a linked list with next and random pointer in O(1) space\",\"datePublished\":\"2021-09-14T11:27:21+00:00\",\"dateModified\":\"2022-11-22T06:10:34+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/\"},\"wordCount\":1092,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/\",\"name\":\"Clone a linked list with next and random pointer in O(1) space | Linked List | Prepbytes\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png\",\"datePublished\":\"2021-09-14T11:27:21+00:00\",\"dateModified\":\"2022-11-22T06:10:34+00:00\",\"description\":\"Learn the most efficient way to clone a linked list with next and random pointer. This blog explains the most efficient approach to rearrange a given linked list in place.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#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\":\"Clone a linked list with next and random pointer in O(1) space\"}]},{\"@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":"Clone a linked list with next and random pointer in O(1) space | Linked List | Prepbytes","description":"Learn the most efficient way to clone a linked list with next and random pointer. This blog explains the most efficient approach to rearrange a given linked list in place.","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\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/","og_locale":"en_US","og_type":"article","og_title":"Clone a linked list with next and random pointer in O(1) space | Linked List | Prepbytes","og_description":"Learn the most efficient way to clone a linked list with next and random pointer. This blog explains the most efficient approach to rearrange a given linked list in place.","og_url":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-09-14T11:27:21+00:00","article_modified_time":"2022-11-22T06:10:34+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.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\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Clone a linked list with next and random pointer in O(1) space","datePublished":"2021-09-14T11:27:21+00:00","dateModified":"2022-11-22T06:10:34+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/"},"wordCount":1092,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/","url":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/","name":"Clone a linked list with next and random pointer in O(1) space | Linked List | Prepbytes","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png","datePublished":"2021-09-14T11:27:21+00:00","dateModified":"2022-11-22T06:10:34+00:00","description":"Learn the most efficient way to clone a linked list with next and random pointer. This blog explains the most efficient approach to rearrange a given linked list in place.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000672037-Article_135.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/clone-a-linked-list-with-next-and-random-pointer-in-o1-space\/#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":"Clone a linked list with next and random pointer in O(1) space"}]},{"@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\/4906","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=4906"}],"version-history":[{"count":7,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4906\/revisions"}],"predecessor-version":[{"id":10674,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4906\/revisions\/10674"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=4906"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=4906"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=4906"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}