struggler
BAN USERThere is something called cycle leader iteration which can be used for this.
The pre-requisite for this is that the size array should be in 3^k+1 format. If the input array is not of that length then the array need to be broken in multiple subarrays to get this format for all arrays.
Once that is done cycle leader iteration can be applied on each array individually and then merge them to get final output.
getKthLargestInLL( linkedList, K ){
for( int i = 1; i<= K; i++ ){
NODE node = findMax( linkedList );
if( node == linkedList )
linkedList = linkedList.next;
}
}
NODE findMax( linkedList ){
Node maxNode = null;
Node preMaxNode = null;
Node lastNode = null;
while( linkedList != null ){
if( maxNode == null || maxNode.data < linkedList.data ){
maxNode = linkedList;
preMaxNode = lastNode;
}
lastNode = linkedList;
linkedList = linkedList.next;
}
if( lastNode != null )
lastNode.next = maxNode.next;
return maxNode;
}
reArrange(ll){
aList= ll;
while(ll.data != b1 )
ll = ll.next;
bList = ll;
ll = aList; //initialized ll to original start
while( aList != null && bList != null ){
aListNextNode = aList.next;
aList.next = bList ;
aList = aListNextNode;
bListNextNode = bList.next;
bList.next = aListNextNode;
bList = bListNextNode;
}
return ll;
}
Division not allowed. Constraint!!
- struggler March 09, 2014