Given singly linked list with every node having an additional “arbitrary” pointer that currently points to NULL. We need to make the “arbitrary” pointer to greatest value node in a linked list on its right side.
A Simple Solution 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(n2).
An Efficient Solution can work in O(n) time. Below are steps.
- Reverse given linked list.
- 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.
- Reverse modified linked list and return head.
C++ Programming:
[pastacode lang=”cpp” manual=”%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” message=”” highlight=”” provider=”manual”/]Output:
Resultant Linked List is: Node Next Pointer Arbit Pointer 5 10 10 10 2 3 2 3 3 3 NULL NULL
Recursive Solution:
We can recursively reach the last node and traverse the linked list from end. Recursive solution doesn’t 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.
C++ Programming:
[pastacode lang=”cpp” manual=”%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” message=”” highlight=”” provider=”manual”/]Output:
Resultant Linked List is: Node Next Pointer Arbit Pointer 5 10 10 10 2 3 2 3 3 3 NULL NULL