CareerCup

swap Nodes values instead

Merge sort is best suited for linked list.

Follow this link for explanations and implementation:
geeksforgeeks.org/archives/7740

Doesn't mergesort inherently uses extra nodes?

Yeah thanks.. realized that.. :)

Quick sort is pretty efficient and doesn't use any other node, just swapping

/*
 Hint: Do not allow using additional node, but is it allowed to use additional node values?
 */

#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef struct NodeT {
  int data;
  NodeT *right;
}Node;


void swapNode(Node *l, Node *r)
{
  int tmp = l->data;
  l->data = r->data;
  r->data = tmp;
}

Node * newNode(int num)
{
  Node * node = new Node();
  node->data = num;
  node->right = NULL;
  return node;
}

Node * appendNode(Node *root, int data)
{
  if (root == NULL) {
    return newNode(data);
  }
  
  Node *node = newNode(data);
  
  root->right = node;
  
  return node;
}

Node * sortList(Node *head, int n)
{
  if (head == NULL || head->right == NULL || n <= 1) {
    return head;
  }

  int randIndex = rand() % n;
  
  Node *target = head;
  
  for (int i = 0; i < randIndex; i ++) {
    if (target) {
      target = target->right;
    }
  }
  
  swapNode(head, target);
  
  int i = 1, count = 0;
  Node *tail = head;
  for (Node *iter = head->right; i < n && iter; i ++, iter = iter->right) {
    if (iter->data < head->data) {
      count ++;
      tail = tail->right;
      swapNode(tail, iter);
    }
  }
  
  swapNode(head, tail);
  
  head = sortList(head, count);
  tail->right = sortList(tail->right, n - count - 1);
  
  return head;
}

void printList(Node *head, int n)
{  
  if (!head) {
    return;
  }
  
  for (int i = 0; i < n && head; i ++) {
    cout << head->data << " ";
    head = head->right;
  }
  
  cout << endl;
}

void cleanList(Node *root)
{
  if (root == NULL) {
    return;
  }
  
  cleanList(root->right);
  
  root->right = NULL;
  root->data = 0;
  
  delete root;
}

int main()
{
  int a[1000];
  int n = 100;
  while (cin >> n && n != 0) {
    if (n > 1000) {
      break;
    }
    
    for (int i = 0; i < n; i ++) {
      a[i] = i;
    }
    
    for (int i = 0; i < n; i ++) {
      int r = rand() % n;
      int tmp = a[i];
      a[i] = a[r];
      a[r] = tmp;
    }
    
    Node *head = NULL;
    head = appendNode(head, a[0]);
    Node *last = head;
    
    for (int i = 1; i < n; i ++) {
      last = appendNode(last, a[i]);
    }
  
    head = sortList(head, n);
    printList(head, n);    
    cleanList(head);
  }
  
  return 0;
}

def sort_link_list(head_node):
    while (True):
        curr = head_node
        changed = False
        while (curr.next_node is not None):
            if (curr.value < curr.next_node.value):
                curr.value = curr.value ^ curr.next_node.value
                curr.next_node.value = curr.value ^ curr.next_node.value
                curr.value = curr.value ^ curr.next_node.value
                changed = True
            curr = curr.next_node
        if (not changed):
            break

mergesort for link lists does not use extra space...
it is an in place algorithm...
so O(nlogn)

//programme by shivi
#include<iostream>
#include<conio.h>
using namespace std;
class LinkList
{
private:
struct Node
{
int item;
Node* next;
Node(int k,Node* x)
{
item=k;
next=x;
}
};
Node* start;

public:
LinkList()
{
start=NULL;
}

void AddNode(int key)
{
Node *p=new Node(key,start);
start=p;
}

void Print()
{
pr(start);
}

void pr(Node *x)
{
if(x==NULL)return;
pr(x->next);
cout<<x->item<<" ";
}

void MergeSort()
{
mergesort(&start);
}

void mergesort(Node **start)
{
Node *x=*start,*lo,*mid;
if(x->next==NULL || x==NULL)
return;

splitlist(*start,&lo,&mid);
mergesort(&lo);
mergesort(&mid);
*start=mergelist(lo,mid);
}

void splitlist(Node *start,Node **lo,Node** mid)
{
if(start==NULL || start->next==NULL)
{
*lo=start;*mid=NULL;
}

else
{
Node *a=start,*b=start->next;

while(b!=NULL)
{
b=b->next;
while(b!=NULL)
{
a=a->next;
b=b->next;
}
}
*lo=start;
*mid=a->next;
a->next=NULL;
}

}

Node* mergelist(Node *lo,Node *mid)
{
Node *newstart=NULL;
if(lo==NULL)
return mid;
if(mid==NULL)
return lo;

if(lo->item>=mid->item)
{
newstart=lo;
newstart->next=mergelist(lo->next,mid);
}

else
{
newstart=mid;
newstart->next=mergelist(lo,mid->next);
}
return newstart;
}


bool CheckIdenticalLinkLists(Node * a,Node* b)
{
if(a==NULL && b==NULL)
return 1;
else if(a==NULL && b!=NULL)
return 0;
else if(a!=NULL && b==NULL)
return 0;
else if(a->item!=b->item)
return 0;

return CheckIdenticalLinkLists(a->next,b->next);
}

void alternate()
{
Node*a,*b;
AlternateSplit(start,&a,&b);
pr(a);
cout<<endl;
pr(b);
}

void AlternateSplit(Node *start,Node** a,Node** b)
{
Node *s1=start,*s2=start->next,*x=s1,*y=s2;
if(start==NULL || start->next==NULL)
{
*a=start;
*b=NULL;
}

else
{
while(b || a)
{
x->next=y->next;
x=x->next;
y->next=x->next;
y=y->next;
}

}

if(x->next!=NULL) x->next=NULL;
if(y->next!=NULL) y->next=NULL;
*a=s1;
*b=s2;
}
};
int main()
{
LinkList l;
LinkList k;
l.AddNode(2);
l.AddNode(1);
l.AddNode(4);
l.AddNode(6);
l.AddNode(3);
l.AddNode(9);
k.AddNode(2);
k.AddNode(5);
k.AddNode(19);
k.AddNode(6);
k.AddNode(8);
k.AddNode(1);
l.Print();
cout<<endl;
// l.Print();cout<<endl;k.Print();
l.MergeSort();//k.MergeSort();
//cout<<endl;
l.Print();cout<<endl;//k.Print();
//l.alternate();
}

I like the first answer to simply swap the value. Alternately, if we aren't even allowed to use a second variable, and assuming the singly linked list contains only numbers as data, we can use the typical math operations to swap the values.
a=21, b=5
1. a=a+b (a becomes 26)
2. b=a-b (b becomes 21)
3. a=a-b (a becomes 5)

This post is in reference to my previous response above where I'm wondering why some links say that heapsort for linked list is nearly impossible.
Here I provide an algortihm that runs in O(nlogn) time. Most of the algortihm is taken from cormen's book except the method 'heapsort'

Pseudo algorithm and runtime calculation for heapsort (ascending order) for a linked list (with single forward pointer/ref)
-------------------------------------------------------------------------
heapsort(Node h) {//first time invoke this with head of the list
   n=get_length_of_list(h);  //runs in O(n)
   build_max_heap(h);     //runs in O(nlogn)

   //handle max element of the entire list which would be the tail after sorting in ascending order
   Node h_dash=h->next;  //no additional node just a temporary variable thus fixed memory O(1)
   h->next=h->next->next;  //null check for h->next and returning is omitted for simplicity
   h_dash->next=null;     //ensure tail’s next field points to null

   //now we keep on max_heapify the rest of the list and keep removing the max element from
   //	head of the given list and subsequently adding them to the head of the new list identified by
   //h_dash
   while h->next != null
        max_heapfy(h);  //runs in O(logn)
        Node t=h_dash  //another temporary variable ensuring O(1) memory
        h_dash=h->next;
        h->next=h->next->next; //null check not required since h->next is not null
        h_dash=t;
   end-while
   //point the new list to the original head
  h->next=h_dash;
----------------------------------

build_max_heap(Node h){ //runs in n times of runtime-of(max_heapfy) i.e. O(nlogn)
   n=get_length_of_list(h);  //this need not to be calculated again and can be passed as argument
   for i from (n/2) downto 1 //indexing starts from 1 at head to n in the tail side.
      max_heapify(h, i);      //runs in O(logn) time 
   end-for
----------------------------------

max_heapify(Node h, int i, int n){ //see below
   l=left_child_index(i)       //runs in O(1)
   r=right_child_index(i)      //runs in O(1)
  
   if l <= n and element_at(l) > element_at(i)  //runs in O(n)
      largest=l  //we can also improve by storing the largest value in another variable, but omitted here 
   else
      largest=i
   end-if

   if r <= n and element_at(r) > element_at(largest)  //runs in O(n)
      largest=r
   end-if

  if largest != i
	 swap element_at(i) with element_at(largest)   //can be made O(1) we store relevant references during previous visits, but here it is O(n)
       max_heapify(h, largest);
  end-if

Run time of max heapify is:
T(n)= O(n) + O(n) + O(n) + T(2n/3)  //with this algortihm
    = O(n) + T(2n/3)               //see cormen et. al. on why 2/3 of n
    = O(nlogn)

Thus we see even for a linked list with forward pointer/ref we can have worst case heapsort time as O(nlogn) which is same as for an array.

Find Max and swap with last node and so on is the simplest solution I guess.

/**
I am using pointers but no extra node for sorting link list
*/

void LinkList::sort() {
Node*out_loop= head, *q=NULL, *p=head, *r=NULL;

while(out_loop!=NULL)
{
q=p;
while(q->next!=NULL) {
r=q->next;
//cout << q->data<<endl;
if(q->data > r->data) {
q->next=r->next;
r->next=q;
if(q==head) {
head = r;
p=r;
} else {
p->next=r;
p=r;
}
}else{
p=q;
q=q->next;
}
}
p=head;
out_loop=out_loop->next;
}
}

Node mergeSort(Node head){
	if (head == null || head.next == null)
		return head;
	Node mid = getMidNode(head);
	Node secondHalf_head = mid.next;
	mid.next = null;
	return merge(mergeSort(head) , mergeSort(secondHalf_head));
}

Node merge(Node head1 , Node head2){
	Node current;
	Node head;
	Node temp1 = head1;
	Node temp2 = head2;
	if (head2.content < head1.content){
		current = head2;
		head = head2;
		temp2 = temp2.next;
	}else{
		current = head1;
		head = head1;
		temp1 = temp1.next;
	}
	while (temp1 != null & temp2 != null){
		if (temp1.content <= temp2.content){
			current.next = temp1;
			temp1 = temp1.next;
		}else{
			current.next= temp2;
			temp2 = temp2.next;
		}
	}
	if (temp2 != null)
		current.next = temp2;
	else
		current.next = temp1;
	return head;
}

Node getMidNode(Node head){
	Node slow = head;
	Node fast = head;
	while (fast != null && fast.next != null){
		slow = slow.next;
		fast = fast.next.next;
	}
	return slow;
}

{
{
{
#include<stdio.h>
#include<malloc.h>
struct Node{
int data;
struct Node *next;
}*head=NULL;
void input(int);
void show();
main()
{
int value;
char choise='y';
while(choise=='y'||choise=='Y')
{
printf("\n Enter integer values:-");
scanf("%d",&value);
input(value);
fflush(stdin);
printf("\n Enter another elemenet(y/n):-");
scanf("%c",&choise);
}
show();
}
void show()
{
printf("\n");
struct Node *temp=head;
while(temp!=NULL)
{
printf(" %d",temp->data);
temp=temp->next;
}

}

void input(int value)
{
struct Node *temp=head,*element=(struct Node*)malloc (sizeof(struct Node));
element->data=value;
if(head==NULL)
{
element->next=head;

head=element;
}
else if(value<=temp->data)
{
element->next=temp;
head=element;
}
else
{
while(temp!=NULL)
{
if(temp->data>=value)
{
element->next=temp->next;
temp->next=element;
break;
}

else if(temp->next==NULL&&temp->data<=value)
{
temp->next=element;
element->next=NULL;
break;
}
else if( temp->data<= value &&temp->next!=NULL &&temp->next->data>=value)
{
element->next=temp->next;
temp->next=element;
break;
}
temp=temp->next ;

}
}
}
/*
output

Enter integer values:-5

Enter another elemenet(y/n):-y

Enter integer values:-34

Enter another elemenet(y/n):-y

Enter integer values:-45

Enter another elemenet(y/n):-y

Enter integer values:-32

Enter another elemenet(y/n):-y

Enter integer values:-9

Enter another elemenet(y/n):-y

Enter integer values:-34

Enter another elemenet(y/n):-y

Enter integer values:-563

Enter another elemenet(y/n):-y

Enter integer values:-45

Enter another elemenet(y/n):-n

5 9 32 34 34 45 45 563
-------------------------------
*/
}
}
}