CareerCup

//Sort a linklist using merge sort
//We will change nodes pointer to make it sorted
//Rewrite merge function such a way that we not need to use merge_util
// as helper

struct Node
{
  int data;
  Node *next;
  Node(int d, Node* temp) : data(d),next(temp)
  {

  }
};

void Insert(Node** head,int data)
{
   if(*head == NULL)
   {
       *head = new Node(data,NULL);
   }
   else
   {
      Insert(&((*head)->next),data);
   }
}

void print(Node *head)
{
   while(head != NULL)
   {
      cout<<head->data<<"  ";
      head = head->next;
   }
}

//Other version of middle we should not use which return
//n/2+1 th node as middle
//Subproblem1=>[head,mid]
//Subproblem2=>[mid+1,end)
//else there will be a infinite loop when item are 2
Node* middle(Node *head)// mid = n/2 th node
{
   if(head == NULL || head->next == NULL)
   {
       return head;
   }

   Node* slow = head;
   Node* fast = head;

   while(fast && fast->next)
   {
       fast = fast->next->next;
       if(fast == NULL) break;
       slow = slow->next;
   }
   return slow;
}

Node* merge(Node* head1, Node* head2)
{
    if(head1 == NULL) return head2;
   
    if(head2 == NULL) return head1;

    Node *result = NULL;
   
    if(head1->data <= head2->data)
    {
        result = head1;
        result->next = merge(head1->next,head2);
    }
    else
    {
       result = head2;
       result->next = merge(head1,head2->next);
    }
    return result;
}

void merge_util(Node** head1,Node **head2)
{
   *head1 = merge(*head1,*head2);
   *head2 = NULL;
}
void merge_sort(Node** head)
{
   // min size of subproblem is 2 size so if 2 or more element then call it
   if((*head)->next != NULL)
   {
       Node *mid = middle(*head);

       Node *second = mid->next;
       mid->next = NULL;

       merge_sort(head);
       merge_sort(&second);
       merge_util(head,&second);
   }
}

int main()
{

   Node* head = NULL;

   Insert(&head,5);
   Insert(&head,4);
   Insert(&head,3);
   Insert(&head,2);
   Insert(&head,-1);
   Insert(&head,-2);
   Insert(&head,-3);
   Insert(&head,-4);
   merge_sort(&head);
   print(head);
   return 0;
}

You meant that final list should be sorted?

We can use merge sort here if we want do using link modify, if the problem is we can modify data itself then this question is easy and we can use bubble sort of selection sort...i will post solution soon both ways......

We can use simple Bubble sort.

public void sort(Node head) {
	cur = Head;
	cur_next = cur.next;
	count = 0;

	while(cur != null) {
		cur= cur.next;
		count++;
	}

	for(int i = 0;i < count ;i++){
		cur = head;
		cur_next = cur.next;
		
		for(int j = 0;j < i;j++) {
			if(cur.value < cur_next.value){
				swap_values(cur,cur_value);
			}
		}
	}
}

I guess the question is just about sorting a linked list based on the values present in the node. It can be done by bubble sort as mentioned by glebstepanov1992

//bubble sort approach

void bubble_sort(Node* head)
{
   if(head == NULL || (head)->next == NULL)
   {
       return;
   }

   int count = 0;
 
   Node* temp = head;
   while(temp != NULL)
   {
       count++;
       temp = temp->next;
   }
   

   Node *p = NULL;
   Node *q = NULL;
   bool flag = false;

   for(int i = count-1; i > 0; --i)
   {
       p = head;
       q = head->next;
       flag = false;

       for(int j = 0; j < i; j++)
       {
          if(p->data > q->data)
          {
             flag = true;
             swap(p->data,q->data);
          }
          p = p->next;
          q = q->next;
       }

       if(flag == false) break;
       
   }
}

Already all the nodes in the list are pointing to the other. So finding the head of the node will solve the problem. I assume it will take n^2 time complexity.

To all people saying bubble sort: you would have failed a Microsoft interview lol

Item* mergesort(Item* top) {
  if (!top || !top->next)
    return top;

  Item* middle = top; 
  for (Item* p = top; p->next && p->next->next; p = p->next->next)
    middle = middle->next;

  Item* left_last = middle;
  middle = middle->next;
  left_last->next=NULL;
  
  Item* left = mergesort(top);
  Item* right = mergesort(middle);
  
  Item** curr = ⊤
  while (left || right) {
    if (!right ||
        (left && left->data <= right->data)) {
      *curr = left;
      left = left->next;
    } else {
      *curr = right;
      right = right->next;
    }
    curr = &(*curr)->next;
  }
  return top;
}

This is a topological sort problem. It can be solved in O(n) time by loading the array into a HashSet and using DFS.

Just use two stacks. On stack1 push the first element. Go to the next element and then push to the stack. Make sure the n-element is less than (n-1)element. Use the other stack2 as buffer.