Machinist
BAN USERWe can solve this in o(n) using a global pointer and recursion. Initially let the global pointer point to head. Recursively (important ) iterate through the Linked List and during return calls (which will be automatically in reverse order) append the current node to the Node referred by global pointer. Incrremant the Global pointer twice.Do this until the current node and global pointer are same. Although, because of recursion the space used is not O(1).
//globals
private static Node cur;
private static boolean solved=false;
//recursive method
private static void solve(Node root){
if(root.next!=null)
solve(root.next);
if(root!=cur && !solved){
Node tmp=cur.next;
cur.next=root;
root.next=tmp;
cur=cur.next.next;
}else{
cur.next=null;
solved=true;
}
}
Iterate over the array and for each item reduce the problem to classic "pairs with sum" problem.
E.g. For [-1,-3,4,5] for first item -1 find all the pairs in remaining [-3,4,5] whose sum is 0-(-1) =1. You can use HashMap to find the pairs. The time eff. would be O(n^2).
Do BFS on every 1's. While doing BFS make sure that all the vertices at a certain level has only one "not visited" adjacent vertex.If any of the vertices at that level has more than one "not visited" vertices then move on.
- Machinist December 19, 2016