CareerCup

Merge Sort on the linked list by modifying the next_larger pointer. The merge sort on linked list doesn't need any auxiliary memory.

1) Push the first element to stack.
2) Pick rest of the elements one by one and follow following steps in loop.
....a) Mark the current element as next.
....b) If stack is not empty, then pop an element from stack and compare it with next.
....c) If next is greater than the popped element, then next is the next greater element fot the popped element.
....d) Keep poppoing from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
....g) If next is smaller than the popped element, then push the popped element back.
3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them

public static void main(String...s)
{




public static void main(String…s)
{
Node headNode; //this instance variable always points to the starting Node of the list
Node currentNode=headNode;//this instance variable always points to the node currently for which we are finding the next_larger mode
Node movingPointer;//this instance variable is a helper pointer which moves the whole list for every node

while(currentNode!=null)
{
movingPointer=headNode;
while(movingPointer!=null)
{
if(movingPointer.data > currentNode.data)
{
if(currentNode.next_larger!=null)
{
if(movingPointer.data < currentNode.next_larger.data)
{
currentNode.next_larger.data= movingPointer.data;
}
}
else
currentNode.next_larger.data= movingPointer.data;
}
movingPointer= movingPointer.next;
}
currentNode=currentNode.next;
}

}


PS: Solution 2:
Since there is no space limitation to your question, copy all the nodes into an array and sort it.Example,for the list 4-->8-->2-->1-->9, sorted array would be [1 2 4 8 9].
As, we traverse the list from the start to end, for each node, we will find the next largest element from the array, which is the consecutive element. Search the list and assigned that node to next larger.






}

In the above comment, in the solution 2, u will have simultaneously a list and array. U will traverse the list, while sorted array of nodes is used for finding the next largest element easily.

void print(node *head){
		while(head!=NULL){
			printf("%d->",head->data);
			head=head->next;
		}
		printf("NULL\n");
}

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
typedef struct x{
	int x;
	struct x *next;
	struct x *nextLarger;
}node;	

node *create(){
	int n;
	node *head=NULL;
	int flag=0;
	node *start=NULL;
	scanf("%d",&n);
	while(n--){
		if(flag==0){
			head=(node*)malloc(sizeof(node));
			scanf("%d",&(head->x));
			head->nextLarger=NULL;
			head->next=NULL;
			start=head;
			flag=1;
		}	
		else{
				head->next=(node*)malloc(sizeof(node));
				head=head->next;
				scanf("%d",&(head->x));
				head->nextLarger=NULL;	
				head->next=NULL;
		}
	}
	
	return start;
}

void print(node *head){
		while(head!=NULL && head->nextLarger!=NULL) {
			printf("%d->%d\n",head->x,head->nextLarger->x);
			head=head->next;
		}
		
}
int main(){
	node *head=NULL;
	head=create();
	//print(head);
	
	
	stack<node*>s;
	s.push(head);
	node *tmp=NULL;
	while(s.size()>0){
		tmp=s.top();
		//cout<<tmp->x<<endl;
		node *q=tmp->next;
		if(q!=NULL){
			if(q->x>tmp->x){
				s.pop();
				tmp->nextLarger=q;
				s.push(q);
			}else{
				s.push(q);
			}	
		}else{
			s.pop();
			break;
				
		}
	}
	while(s.size()>0){
		if(s.top()->x<tmp->x){
			s.top()->nextLarger=tmp;
		}	
		s.pop();
	}	
	
	print(head);
	return 0;	
}

@Lesnar : your code is not working for the test case following test case:
          4->8->2->1->9->5->6

The above code represents the functionality of a skip lists

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
typedef struct x{
	int x;
	struct x *next;
	struct x *nextLarger;
}node;	

node *create(){
	int n;
	node *head=NULL;
	int flag=0;
	node *start=NULL;
	scanf("%d",&n);
	while(n--){
		if(flag==0){
			head=(node*)malloc(sizeof(node));
			scanf("%d",&(head->x));
			head->nextLarger=NULL;
			head->next=NULL;
			start=head;
			flag=1;
		}	
		else{
				head->next=(node*)malloc(sizeof(node));
				head=head->next;
				scanf("%d",&(head->x));
				head->nextLarger=NULL;	
				head->next=NULL;
		}
	}
	
	return start;
}

void print(node *head){
		while(head!=NULL) {
			if(head->nextLarger)	
				printf("%d->%d\n",head->x,head->nextLarger->x);
			head=head->next;
		}
		
}
int main(){
	node *head=NULL;
	head=create();
	//print(head);
	
	
	stack<node*>s;
	s.push(head);
	node *tmp=NULL;
	while(s.size()>0){
		tmp=s.top();
		//cout<<tmp->x<<endl;
		node *q=tmp->next;
		if(q!=NULL){
			if(q->x>tmp->x){
				s.pop();
				tmp->nextLarger=q;
				while(s.size()>0){
					node *q1=s.top();
					if(q1->x<q->x){
						q1->nextLarger=q;
						s.pop();
					}else
						break;
				}		
				s.push(q);
			}else{
				s.push(q);
			}	
		}else{
			s.pop();
			break;
				
		}
	}
	while(s.size()>0){
		if(s.top()->x<tmp->x){
			s.top()->nextLarger=tmp;
		}	
		s.pop();
	}	
	
	print(head);
	return 0;	
}

@ Algorithmist thanks for the correction.

@ Algoseeker try to dry run it ...its a simple application of stack...

1. reverse the link list in one pass

2.starting from ptr = new head//start filling next_larger from new head.End of original link list becomes new head

ptr->next_larger=NULL
prev = ptr
while (ptr->next != NULL)
{
if (prev->data > ptr->data )
ptr->next_larger = prev
else
{
NXT_LARGER = prev->next_larger
while (NXT_LARGER != NULL && NXT_LARGER->data < ptr->data)
NXT_LARGER = NXT_LARGER->next_larger
ptr->next_larger = NXT_LARGER
}
prev = ptr
ptr = ptr->next
}
3. reverse the link list again in 1 pass

i think that for linked list the O(n^2) approach would be better...its code is as fllows

void updateNextLarger(struct node ** head)
{
struct node * curr = *head;
while(curr)
{
struct node * nextNode = curr->next;
while(nextNode)
{
if(curr->data > nextNode->data)
{
curr->nextLarger = nextNode;
break;
}
nextNode = nextNode->next;
}
curr = curr>next;
}
}

if any better approach is there...then please let us know...any mistakes in the code are also welcome...

Parse the linked list from one end with four Variables Min, Second_Min, Max, Second Max all initialised to zero.
(a)Find the values for all these variables in one pass. Then make min->nextgreater = Second_min , Second_Max->nextgreater = Max. Consider only nodes with Null value in the Nextgreater field during parsing.
(b)Now Initialize all four variables with second_Min.

Repeat step (a)& (b) logn times .

Please Correct me if am wrong.

Sorry ,In my solution Variables Min, Second_Min, Max, Second Max all must be initialised to first element in the linked list at the beginning.

list = head;
while(!list) {
list1 = head;
while (!list1) {
temp = NULL;
if(list->data<list1->data) {
if (!temp)
temp = list1;
else if(list1->data<temp->data)
temp = list1;
}
list1=list1->next;
}
list->next_larger = temp;
list = list->next;
}

This solution is basic sortedInsert but this time we modify the nextLarger pointer instead of next pointer.

void InsertSort(struct node* headRef) {
struct node* result = NULL; // build the answer here
struct node* current = headRef; // iterate over the original list

while (current!=NULL) {
SortedInsert(&result, current);
current = current->next;
}
}


void SortedInsert(struct node** headRef, struct node* newNode) {
// Special case for the head end
if (*headRef == NULL || (*headRef)->data >= newNode->data) {
newNode->nextLarger = *headRef;
*headRef = newNode;
}
else {
// Locate the node before the point of insertion
struct node* current = *headRef;
while (current->nextLarger!=NULL && current->nextLarger->data<newNode->data) {
current = current->nextLarger;
}
newNode->nextLarger = current->nextLarger;
current->nextLarger = newNode;
}
}