Kartik Agarwal
BAN USERUndergraduate from BPIT
You have to take 2 stacks for this.
We can use one stack for printing from left to right and other stack for printing from right to left.
The implementation does not return the list of list.. but you can modify a bit to return that.
For now, I am printing the elements as desired instead of returning list of list
public void levelOrderTraversal()
{
if(root==null)
{
System.out.println("Empty tree");
return;
}
Stack <Node> s1=new Stack<>();
Stack <Node> s2=new Stack<>();
s1.add(root);
while(!s1.isEmpty()||!s2.isEmpty())
{
while(!s1.isEmpty())
{
Node temp=s1.pop();
System.out.print(temp.info+" ");
if(temp.right!=null)
s2.push(temp.right);
if(temp.left!=null)
s2.push(temp.left);
}
System.out.println("");
while(!s2.isEmpty())
{
Node temp=s2.pop();
System.out.print(temp.info+" ");
if(temp.left!=null)
s1.push(temp.left);
if(temp.right!=null)
s1.push(temp.right);
}
System.out.println("");
}
}
Note: you cannot implement XOR linked list with java because unreferenced nodes will be garbage collected!
The solution can be to use an array of type Node to keep a reference to each node to avoid garbage collected from picking them up.
But this would take a lot of extra space.
So implementation goes to C/C++ and other languages.
Its really simple:
what you have to do is:
1) take the next node's value in this node.
2) delete the next node.
if the given node is the last node then handle separately.
code using java.
public void delNode(Node curr)
{
if(curr.next==null)
{
curr=null; // in case curr is last
return;
}
curr.info=curr.next.info;
curr.next=curr.next.next;
}
Its simple.. Perform merge sort for linked list.
In case of array it is not inplace but for Linked List merge sort is in place algorithm.
Solution can be found on geeksforgeeks website.
Done using reservoir sampling
-Consider a linked list whose length is not known.
-for 1st node, probability is 100%, for second 50% and so on..
-doing this n times would give an equal probability for each node.
Here is my code:
public int findrandom()
{
Node curr=start;
int count=1, result=0, probability;
Random rand=new Random();
while(curr!=null)
{
probability=rand.nextInt(count)+1;
if(count==probability)
result=curr.info;
count++;
curr=curr.next;
}
return result;
}
All the operations will be done in O(1) time and O(1) space.
We gonna use a Doubly linked list.
-a pointer to keep lowest value record.
-top value can be easily fetched any time.
-a pointer to keep track of middle element based on a counter value(containing no. of nodes)
Whenever a node is added or popped the mid pointer is checked if it shall be moved or not.
- Kartik Agarwal September 27, 2017