using stack, the problem can be solved in O(n) time. here is the algo :-
1- push first node in stack. mark next node as current
2 - start from current element and check if the node on top of stack is
smaller than current , then pop the node and make its next_largest pointer
set to current. Do
@Algo-Geek : this wont work , as requirement of the problem is different .
even i misunderstood the problem and posted the algo above doing the same
as you have mentioned , but question doesn't say next larger element on
right side. It just ask for next larger element cud be on left or cud be on
@atul: we always need to point at the next larger node..so that is ruled
out.
On Sat, Mar 24, 2012 at 10:14 AM, Atul Singh atulsingh7...@gmail.comwrote:
I couldn't understand the meaning of *return the pointer to smallest*
Is it that that the pointer of largest node will point to smallest
can anyone explain vividly how we can use merge sort here. thank you.
On Sat, Mar 24, 2012 at 1:54 PM, Sambhavna Singh coolsambha...@gmail.comwrote:
@atul: we always need to point at the next larger node..so that is ruled
out.
On Sat, Mar 24, 2012 at 10:14 AM, Atul Singh
@Atul: after u sort the list the head pointer will automatically point to
the smallest element so u actually return the head of the list.
@Sambhavna:
here is the Pseudoccode (More or less similar to, doing merge sort for
arrays):
Mersgesort(node ** list){
if( head==NULL or head- next ==
@Abhishek: What sorting algorithm are you going to use?
On Mar 23, 3:02 pm, Abhishek Sharma jkabhishe...@gmail.com wrote:
It is basically sorting the linked list. Do not change the first pointer of
nodes and use the second pointer for sorting. return the pointer to the
smallest element. That's
A merge sort will be O(n*log n) and not use the extra memory required
for a heap.
Don
On Mar 23, 3:11 pm, Ashish Goel ashg...@gmail.com wrote:
actually, multimap can be avoided, each element of heap is key,value where
key is the element and value is address and build heap on key.
Best Regards
@don: inplace Mergesort can be used. Complexity would be O(nlogn).
@Ashish: Heapsort is reliable but unstable and also, slower.
On Sat, Mar 24, 2012 at 1:49 AM, Don dondod...@gmail.com wrote:
A merge sort will be O(n*log n) and not use the extra memory required
for a heap.
Don
On Mar 23,
I couldn't understand the meaning of *return the pointer to smallest*
Is it that that the pointer of largest node will point to smallest node.
ATul Singh | Final Year | Computer Science Engineering | NIT
Jalandhar | 9530739855
|
--
You received this message because you are subscribed to
