{"id":27587,"date":"2018-04-04T19:34:04","date_gmt":"2018-04-04T14:04:04","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27587"},"modified":"2018-04-04T19:34:04","modified_gmt":"2018-04-04T14:04:04","slug":"cpp-algorithm-point-arbit-pointer-to-greatest-value-right-side-node-in-a-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/cpp-algorithm-point-arbit-pointer-to-greatest-value-right-side-node-in-a-linked-list\/","title":{"rendered":"Cpp Algorithm-Point arbit pointer to greatest value right side node in a linked list"},"content":{"rendered":"<p>Given singly linked list with every node having an additional \u201carbitrary\u201d pointer that currently points to NULL. We need to make the \u201carbitrary\u201d pointer to greatest value node in a linked list on its right side.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignleft size-full wp-image-27604\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Point-arbit-pointer-to-greatest-value-right-side-node-in-a-linked-list.png\" alt=\"Point arbit pointer to greatest value right side node in a linked list\" width=\"638\" height=\"253\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Point-arbit-pointer-to-greatest-value-right-side-node-in-a-linked-list.png 638w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Point-arbit-pointer-to-greatest-value-right-side-node-in-a-linked-list-300x119.png 300w\" sizes=\"(max-width: 638px) 100vw, 638px\" \/><\/p>\n<p>\u00a0<\/p>\n<p>\u00a0<\/p>\n<p>\u00a0<\/p>\n<p>\u00a0<\/p>\n<p>\u00a0<\/p>\n<p>\u00a0<\/p>\n<p>A <strong>Simple Solution<\/strong> is to traverse all nodes one by one. For every node, find the node which has greatest value on right side and change the next pointer. Time Complexity of this solution is O(n<sup>2<\/sup>).<\/p>\n<p>An <strong>Efficient Solution<\/strong> can work in O(n) time. Below are steps.<\/p>\n<ol>\n<li>Reverse given linked list.<\/li>\n<li>Start traversing linked list and store maximum value node encountered so far. Make arbit of every node to point to max. If the data in current node is more than max node so far, update max.<\/li>\n<li>Reverse modified linked list and return head.<\/li>\n<\/ol>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20point%20arbit%20pointers%20to%20highest%0A%2F%2F%20value%20on%20its%20right%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node*%20next%2C%20*arbit%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20reverse%20the%20linked%20list%20*%2F%0ANode*%20reverse(Node%20*head)%0A%7B%0A%20%20%20%20Node%20*prev%20%3D%20NULL%2C%20*current%20%3D%20head%2C%20*next%3B%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20next%20%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20current-%3Enext%20%3D%20prev%3B%0A%20%20%20%20%20%20%20%20prev%20%3D%20current%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20next%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20prev%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20populates%20arbit%20pointer%20in%20every%0A%2F%2F%20node%20to%20the%20greatest%20value%20to%20its%20right.%0ANode*%20populateArbit(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20Reverse%20given%20linked%20list%0A%20%20%20%20head%20%3D%20reverse(head)%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20pointer%20to%20maximum%20value%20node%0A%20%20%20%20Node%20*max%20%3D%20head%3B%0A%20%0A%20%20%20%20%2F%2F%20Traverse%20the%20reversed%20list%0A%20%20%20%20Node%20*temp%20%3D%20head-%3Enext%3B%0A%20%20%20%20while%20(temp%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Connect%20max%20through%20arbit%20pointer%0A%20%20%20%20%20%20%20%20temp-%3Earbit%20%3D%20max%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20max%20if%20required%0A%20%20%20%20%20%20%20%20if%20(max-%3Edata%20%3C%20temp-%3Edata)%0A%20%20%20%20%20%20%20%20%20%20%20%20max%20%3D%20temp%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Move%20ahead%20in%20reversed%20list%0A%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Reverse%20modified%20linked%20list%20and%20return%0A%20%20%20%20%2F%2F%20head.%0A%20%20%20%20return%20reverse(head)%3B%0A%7D%0A%20%0A%2F%2F%20Utility%20function%20to%20print%20result%20linked%20list%0Avoid%20printNextArbitPointers(Node%20*node)%0A%7B%0A%20%20%20%20printf(%22Node%5CtNext%20Pointer%5CtArbit%20Pointer%5Cn%22)%3B%0A%20%20%20%20while%20(node!%3DNULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20node-%3Edata%20%3C%3C%20%22%5Ct%5Ct%22%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(node-%3Enext)%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20node-%3Enext-%3Edata%20%3C%3C%20%22%5Ct%5Ct%22%3B%0A%20%20%20%20%20%20%20%20else%20cout%20%3C%3C%20%22NULL%22%20%3C%3C%20%22%5Ct%5Ct%22%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(node-%3Earbit)%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20node-%3Earbit-%3Edata%3B%0A%20%20%20%20%20%20%20%20else%20cout%20%3C%3C%20%22NULL%22%3B%0A%20%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20endl%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20create%20a%20new%20node%20with%20given%20data%20*%2F%0ANode%20*newNode(int%20data)%0A%7B%0A%20%20%20%20Node%20*new_node%20%3D%20new%20Node%3B%0A%20%20%20%20new_node-%3Edata%20%3D%20data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20new_node%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20Node%20*head%20%3D%20newNode(5)%3B%0A%20%20%20%20head-%3Enext%20%3D%20newNode(10)%3B%0A%20%20%20%20head-%3Enext-%3Enext%20%3D%20newNode(2)%3B%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext%20%3D%20newNode(3)%3B%0A%20%0A%20%20%20%20head%20%3D%20populateArbit(head)%3B%0A%20%0A%20%20%20%20printf(%22Resultant%20Linked%20List%20is%3A%20%5Cn%22)%3B%0A%20%20%20%20printNextArbitPointers(head)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Resultant Linked List is: \r\nNode    Next Pointer    Arbit Pointer\r\n5               10              10\r\n10              2               3\r\n2               3               3\r\n3               NULL            NULL<\/pre>\n<p><strong>Recursive Solution:<\/strong><\/p>\n<p>We can recursively reach the last node and traverse the linked list from end. Recursive solution doesn\u2019t require reversing of linked list. We can also use a stack in place of recursion to temporarily hold nodes. Thanks to Santosh Kumar Mishra for providing this solution.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20point%20arbit%20pointers%20to%20highest%0A%2F%2F%20value%20on%20its%20right%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node*%20next%2C%20*arbit%3B%0A%7D%3B%0A%20%0A%2F%2F%20This%20function%20populates%20arbit%20pointer%20in%20every%0A%2F%2F%20node%20to%20the%20greatest%20value%20to%20its%20right.%0Avoid%20populateArbit(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20using%20static%20maxNode%20to%20keep%20track%20of%20maximum%0A%20%20%20%20%2F%2F%20orbit%20node%20address%20on%20right%20side%0A%20%20%20%20static%20Node%20*maxNode%3B%0A%20%0A%20%20%20%20%2F%2F%20if%20head%20is%20null%20simply%20return%20the%20list%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20%2F*%20if%20head-%3Enext%20is%20null%20it%20means%20we%20reached%20at%0A%20%20%20%20%20%20%20the%20last%20node%20just%20update%20the%20max%20and%20maxNode%20*%2F%0A%20%20%20%20if%20(head-%3Enext%20%3D%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20maxNode%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Calling%20the%20populateArbit%20to%20the%20next%20node%20*%2F%0A%20%20%20%20populateArbit(head-%3Enext)%3B%0A%20%0A%20%20%20%20%2F*%20updating%20the%20arbit%20node%20of%20the%20current%0A%20%20%20%20%20node%20with%20the%20maximum%20value%20on%20the%20right%20side%20*%2F%0A%20%20%20%20head-%3Earbit%20%3D%20maxNode%3B%0A%20%0A%20%20%20%20%2F*%20if%20current%20Node%20value%20id%20greater%20then%0A%20%20%20%20%20the%20previous%20right%20node%20then%20%20update%20it%20*%2F%0A%20%20%20%20if%20(head-%3Edata%20%3E%20maxNode-%3Edata)%0A%20%20%20%20%20%20%20%20maxNode%20%3D%20head%3B%0A%20%0A%20%20%20return%3B%0A%7D%0A%20%0A%2F%2F%20Utility%20function%20to%20print%20result%20linked%20list%0Avoid%20printNextArbitPointers(Node%20*node)%0A%7B%0A%20%20%20%20printf(%22Node%5CtNext%20Pointer%5CtArbit%20Pointer%5Cn%22)%3B%0A%20%20%20%20while%20(node!%3DNULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20node-%3Edata%20%3C%3C%20%22%5Ct%5Ct%22%3B%0A%20%0A%20%20%20%20%20%20%20%20if(node-%3Enext)%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20node-%3Enext-%3Edata%20%3C%3C%20%22%5Ct%5Ct%22%3B%0A%20%20%20%20%20%20%20%20else%20cout%20%3C%3C%20%22NULL%22%20%3C%3C%20%22%5Ct%5Ct%22%3B%0A%20%0A%20%20%20%20%20%20%20%20if(node-%3Earbit)%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20node-%3Earbit-%3Edata%3B%0A%20%20%20%20%20%20%20%20else%20cout%20%3C%3C%20%22NULL%22%3B%0A%20%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20endl%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20create%20a%20new%20node%20with%20given%20data%20*%2F%0ANode%20*newNode(int%20data)%0A%7B%0A%20%20%20%20Node%20*new_node%20%3D%20new%20Node%3B%0A%20%20%20%20new_node-%3Edata%20%3D%20data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20new_node%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20Node%20*head%20%3D%20newNode(5)%3B%0A%20%20%20%20head-%3Enext%20%3D%20newNode(10)%3B%0A%20%20%20%20head-%3Enext-%3Enext%20%3D%20newNode(2)%3B%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext%20%3D%20newNode(3)%3B%0A%20%0A%20%20%20%20populateArbit(head)%3B%0A%20%0A%20%20%20%20printf(%22Resultant%20Linked%20List%20is%3A%20%5Cn%22)%3B%0A%20%20%20%20printNextArbitPointers(head)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Resultant Linked List is: \r\nNode    Next Pointer    Arbit Pointer\r\n5               10              10\r\n10              2               3\r\n2               3               3\r\n3               NULL            NULL<\/pre>\n<div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Cpp Algorithm-Point arbit pointer to greatest value right side node in a linked list-Linked list<br \/>\nGiven singly linked list with every node <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,79478],"tags":[81795,81798,81796,70487,80236,81797,72485,79556],"class_list":["post-27587","post","type-post","status-publish","format-standard","hentry","category-linked-list","category-singly-linked-list","tag-add-1-to-a-number-represented-as-linked-list","tag-arbitrary","tag-distance-between-two-nodes-in-binary-tree","tag-doubly-linked-list","tag-geeksforgeeks","tag-get-the-local-maxima-or-minima-in-array","tag-linked-list-c","tag-linked-list-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27587","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27587"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27587\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}