CareerCup

My guess is for min. space, mergesort should be applied, which is in-place and
O(N log N).
I am trying to come up with the code.

Best solution i think is...
Considering a BST on given inputs

struct node
{
int data;
struct node *next;
struct node *next_larger;
}

So each node has link to next node = (left node if available else NULL) as well as its next highest node = (right node if available else its parent node).

Simple!...

class Node <T>{
	public T data;
	public Node<T> next;
	public Node<T> nextLarge; // To point the next large element in the list

	Node (T t)
	{
		data = t; 
	}
}

	public Node<T> applicationOfMergeSort(Node<T> head)
	{
		if(head == null || head.next == null) return head;
		else
		{
			Node<T> slow = head;
			Node<T> fast = head;

			//Split
			while(fast.next != null)
			{
				fast = fast.next;
				if(fast.next != null)
					fast = fast.next;
				else
					break;

				slow = slow.next;
			}

			Node<T> List1 = head;
			Node<T> List2 = slow.next;
			Node<T> copyL2 = List2;

			slow.next = null;
			// Split complete
			
			// Recursively Split and then merge until we reach a list of sizes 1
			List1 = applicationOfMergeSort(List1);
			List2 = applicationOfMergeSort(List2);

			//Since List1 will ultimately hold the result of merging do lets reset the head to point to List1, 
			//head will be returned as a result of this function
			head = List1; 


			//Merge
			Node<T> prev = null;

			while(List1 != null && List2!= null)
			{
				if((Integer) List1.data < (Integer) List2.data)
				{
					prev = List1;
					List1 = List1.nextLarge;
				}
				else
				{
					Node<T> nextList2 = List2.nextLarge;
					List2.nextLarge = List1;
					if(prev == null)
					{
						head = List2;
					}
					else
					{
						prev.nextLarge = List2;
					}

					prev = List2;
					List2 = nextList2;
				}
			}

			if(List2 != null)
				prev.nextLarge = List2;
			
			// Merging Complete

			// Now make the connection of next pointers, broken earlier in the split step
			slow.next = copyL2;
			return head;
		}
	}

store the linked list value in an array. Sort that array. Now for each data value in linked list find the same data value in array using binary search. After getting the index of data value in sorted array, get next value from array.
complexity will be nlogn

1) Sort the list ( keeping the original unaltered) : n log n
2) Hash the sorted list ( Key = value, Value = Next pointer in sorted list)
3) Walk through the original list, looking up the hash and setting the next->larger to point to the value in the hash.

Time Complexity: O(n log n) Space = 2n

Or you could do an n2 algorithm walking through the list and finding the next larger element for all the elements

class Node {
    int value;
    Node next;
    Node nextbigger;

public void listSort(){

    Node list, current, q, e, tail=null;
    int insize, merges, psize, qsize, i;

    current = this;
    while(current != null){
        current.nextbigger = current.next;
        current = current.next;
    }
    if(this == null)
        return;

    insize = 1;

    list = this;
    while(true){
        current = list;
        list = null;
        tail = null;
        merges = 0;

        while (current != null) {
            merges++;
            q = current;
            psize = 0;
            for (i = 0; i < insize; i++) {
                psize++;
            q = q.nextbigger;
            if (q == null)
                    break;
            }

            qsize = insize;

             while (psize > 0 || (qsize > 0 && q!=null)) {

                /* decide whether next element of merge comes from p or q */
                if (psize == 0) {
		    /* p is empty; e must come from q. */
		    e = q; q = q.nextbigger; qsize--;

		} else if (qsize == 0 || q == null) {
		    /* q is empty; e must come from p. */
		    e = current;
                    current = current.nextbigger;
                    psize--;

		} else if (current.value <= q.value ) {
		    /* First element of p is lower (or same);
		     * e must come from p. */
		    e = current; current = current.nextbigger; psize--;

		} else {
		    /* First element of q is lower; e must come from q. */
		    e = q; q = q.nextbigger; qsize--;

		}


                if (tail != null) {
		    tail.nextbigger = e;
		} else {
		    list = e;
		}

                tail = e;
             }
            current = q;
        }

        tail.nextbigger = null;

        if (merges <= 1)   /* allow for merges==0, the empty list case */
            return ;

        /* Otherwise repeat, merging lists twice the size */
        insize *= 2;

    }

}


}

For each node let next_larger = next, and sort the linked list treating next_larger pointer as next pointer, I think this problem is just sorting a linked list, the interviewer was just being wise, which I think is pretty stupid. It is exactly like following: I have following data structure, where initial_next pointer points to its next element while next pointer all points null, sort the list.

struct node
{
    int data;
    struct node *initial_next;
    struct node *next;
}

The above understanding of the problem is correct.

Here's code to sort the list using merge sort in C. Simple merge sort routine has been modified to sort a linked list. Its a no brainer. The quality of the code isn't great.

typedef struct node
{
	int i;
	struct node* nxt;
	struct node* nxt_higher;
} Node;

Node * mergeSortList(Node *list){
	int len,count;
	Node *trav,*L2,*L1;
	L1 = list;
	len = listlen(list);
	if (len ==2)
	{
		if (list->i > list->nxt->i)
		{
			list->nxt->nxt = list;
			list->nxt=NULL;
		}
		return list;
	}
	if (len == 1){
		return list;
	}
	trav=list;
	count =1;
	while ((trav != NULL) && (count <= len/2))
	{
		trav=trav->nxt;
		count++;
	}
	L2=trav->nxt;
	trav->nxt=NULL;
	return mergelist(mergeSortList(L2), mergeSortList(L1));
}

Node * mergelist(Node *L1, Node *L2)
{
	Node *L3=NULL, *tempnode=NULL,*lastnode=NULL;
	while((L1!=NULL) && (L2!=NULL))
	{
		tempnode = (Node *)malloc(sizeof(Node));
		if (L3 == NULL)
		{
			L3=tempnode;
		}
		if (lastnode != NULL)
		{
			lastnode->nxt = tempnode;
		}
		if ((L1->i) < (L2->i))
		{
			*tempnode = *L1;
			L1=L1->nxt;
		}
		else if ((L1->i) == (L2->i))
		{
			*tempnode = *L1;
			L1=L1->nxt;
			L2=L2->nxt;
		}
		else
		{
			*tempnode = *L2;
			L2=L2->nxt;
		}
		lastnode = tempnode;
	}
	Node *travel =  NULL;
	if (L1 == NULL)
	{
		travel = L2;
	}
	else if (L2 == NULL)
	{
		travel = L1;
	}
	while (travel !=NULL)
	{
		tempnode = (Node *) malloc(sizeof(Node));
		*tempnode = *travel;
		if (L3 == NULL)
		{
			L3=tempnode;
		}
		if (lastnode != NULL)
		{
			lastnode->nxt = tempnode;
		}
		lastnode = tempnode;
		travel=travel->nxt;
	}
	return L3;
}

int listlen( Node *head )
{
	int count =0;
	while( head !=NULL)
	{
		count++;
		head = head->nxt;
	}
	return count;
}

well i feel better idea would be to use max-heap as a priority queue
Insert all the nodes into the list.
Use an additional variable to store the popped node.
Initially its null

for the given list 3-> 1-> 6-> 5-> 4

Pop the first one 6 and point it to the variable so 6-> null
replace the variable with the current node

then pop next.. here 5 and point 5 to the variable so it is 5-> 6
and so on

overall complexity to add and remove from heap is log n and to traverse the list to push it into the tree is n

therefore it is n + logn = n

I think BST is a good solution.

If list is 3->1->6->5->4 then we ll make a BST out of it.

3
next / \nxt_bigger
1 6
/
5
/
4

After creating we'll traverse the tree using inorder then we ll get
1->3->4->5->6

This is the desired result.

The problem can solve in space with time complexity of nlogn.

list* merge(list* l1,list *l2){
if(!l1) return l2;
if(!l2) return l1;
if(l1->data<l2->data){
l1->next_larger = merge(l1->next_larger, l2);
return l1;
}
else{
l2->next_larger = merge(l1, l2->next_larger);
return l2;
}

}

//use the above merge code

list* sort(list* l){
//split l into 2 parts l1,l2
//merge and return the list
}

Does not it look like you have a infinite loop of nodes coming and you need to do insert sorted

1) traverse the list
2) update the Nexthigher pointer based on the insertsorted link list logic

1) Copy the Next pointer value to Greater pointer
2) Sort using mergesort based upon greater pointer

Use min Priority Queue (PQ)
1. Put all number in the PQ - store the node pointer and the data. Min on data
2. Take the min (top most element - say "node")
3. Set the "node"->nextbigger to the top element in the PQ (peek the next element in the PQ)
4. Repeat 2-4 till one element is left in PQ.

Node* merge(Node* first, Node* second)
{
    Node* result = NULL;
    
    if (!first)
        return second;
    
    if (!second)
        return first;
    
    if (first->data() <  second->data()) {
        result = first;
        result->setNextLarger(merge(first->nextLarger(), second));
    }
    else {
        result = second;
        result->setNextLarger(merge(first, second->nextLarger()));
    }
    
    return result;
}

Node* sort(Node* root, int listLength)
{
    if (!root || !root->next() || listLength <= 1)
        return root;
    
    int middle = listLength / 2;
    int index = 0;
    Node* middleNode = root;
    
    while (index < middle) {
        middleNode = middleNode->next();
        index += 1;
    }
    
    return merge(sort(root, middle), sort(middleNode, listLength - middle));
}

it is really easy but asked by smartness hats off to interviewr to ask such easy question with different way good one :)

1. Traverse the link list & do next_large = next; //Means next_large points same next node.
2. Now assume its a single link list, which is having one pointer next_large.
3. Now sort this single link list in ascending order.

You could copy the value of next into next_larger, then sort the list using nlogn algo, then swap values of next and next_larger.