Last active
May 31, 2017 17:09
-
-
Save anil477/f54accafec785b285dbb8f3f869afa0a to your computer and use it in GitHub Desktop.
Point arbit pointer to greatest value right side node in a linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// recursive to point arbitrary pointer to next greater on the right | |
// http://www.geeksforgeeks.org/point-arbit-pointer-greatest-value-right-side-node-linked-list/ | |
class Node { | |
int data; | |
Node next; | |
Node arb; | |
Node(int d) | |
{ | |
data = d; | |
next = null; | |
arb = null; | |
} | |
} | |
class LinkedList | |
{ | |
Node head; // head of list | |
Node maxNode; | |
public void printList() | |
{ | |
Node temp = head; | |
System.out.println( " Print Function "); | |
while (temp != null) | |
{ | |
if(temp.arb == null) | |
System.out.println( " Data: " + temp.data + " Arb " + temp.arb); | |
else | |
System.out.println( " Data: " + temp.data + " Arb " + temp.arb.data); | |
temp = temp.next; | |
} | |
} | |
public static void main(String[] args) | |
{ | |
LinkedList llist = new LinkedList(); | |
llist.head = new Node(5); | |
Node second = new Node(10); | |
Node third = new Node(2); | |
Node fourth = new Node(1); | |
llist.head.next = second; | |
second.next = third; | |
third.next = fourth; | |
llist.printList(); | |
llist.populate(); | |
llist.printList(); | |
} | |
public void populate() | |
{ | |
this.maxNode = null; // can't set in from the main static main function | |
Node temp = this.head; | |
populateArbit(temp); // can't pass the non static head value from static main func | |
} | |
public void populateArbit(Node head) | |
{ | |
if(head == null) | |
{ | |
return; | |
} | |
if( head.next == null) | |
{ | |
this.maxNode = head; | |
return; | |
} | |
populateArbit(head.next); | |
head.arb = this.maxNode; | |
if(head.data > this.maxNode.data ) | |
this.maxNode = head; | |
return; | |
} | |
public void addAtEnd(int data) | |
{ | |
Node node = new Node(data); | |
Node temp = this.head; | |
while(temp.next != null) | |
{ | |
temp = temp.next; | |
} | |
temp.next = node; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment