Merge and sort 2 linked lists

[Olsi009]

Hi guys (again),

Another exercise in Turbo Pascal about linked lists.

Write a program that merges 2 linked lists and sorts elements from the lowest to the greatest.

let suppose the list has this elements

list = ^pointer;
pointer = record
value:integer;
next:list;
end;

Please help, I have an exam after 3 hrs :S
thanks in advance :)

[Duoas]

I'm sorry, but you got too much of a bone from that last one.

Method 1:
Get yourself a large piece of paper and a couple pennies. Draw yourself two lists, like 4 7 9 23 -2 14 5 6 5 1 0 place the pennies at the head of each list (one above the four and one above the six). The pennies represent your current index into each list.

Now, looking only at the numbers at the pennies, copy those numbers over into a new list, properly sorted.

Method 2:
Check out the merge-sort algorithm.

Hope this helps.

[Olsi009]

Look dude,
I have already made that exercise. I just wanted to see how the rest of the world solves it.
Maybe there's a shorter way to do it rather than mine.

thank you anyway for your....help

[Duoas]

Snot and bile, eh? Well, you just earned yourself a spot on my ignore list.

Before I go, though, a little advice: as you've missed several points.

1. Your professor doesn't care what other people can do. Chances are likely that someone, somewhere, will produce better code than either you or I could do.
2. Tough beans if you don't like the answer. Don't pander for code. If you are confused, or genuinely need help, read the forum rules and try again. If you just want to compare algorithms, state it explicitly and post yours first.
3. Don't ask for help, then act rudely toward those spending their valuable time (which is usually much more valuable than yours) trying to help you. Doing so gets you on the negative side of nothing.

[Olsi009]

Douas,
I am really sorry for the reply I gave you but last night when I got back from the exam I was pretty angry with myself (for my results) and I was like shouting to anyone on my way.

Thank you very much for all the help you gave me before,

Have a nice week

[Duoas]

Hmm, OK, you're forgiven. Sounds like you have a lot of tests at once?

[anjaly grace]

merge sort in link list. Works in g++/c++ by deleting // 's

#include<iostream>
using namespace std;
//#include<conio.h>
#include<stdio.h>
#include<malloc.h>



struct node
{
int number;
struct node *next;
};


struct node *adnode(int number, struct node *next);//Adding new node
struct node *mergesort(struct node *head);                 //spliting link list using 2 pointers
struct node *merge(struct node *head_one, struct node *head_two); //merge list1 and list2


int main()
{
struct node *head;
struct node *current;
struct node *next;
int j=0,k,k3;
//  clrscr();
head=NULL;


while(j<4)
{
cout<<"Choice       \n   1.Enter new element   \n   2.Mergesort  \n    3.print list \n  ";
cin>>j;
switch(j)
{
case 1:
cout<<"Enter number    ";
cin>>k3;
head = adnode(k3, head);
break;
case 2:
head = mergesort(head);
break;
case 3:
for(current = head; current != NULL; current = current->next)
cout<< current->number<<",";
cout<<"\n\n";
break;
default:
break;
}                //Quit if value greater than 4
}
for(current = head; current != NULL; current = next)                               //before ending, free list.
next = current->next, free(current);
//  getch();
return(0);
}


struct node *adnode(int number, struct node *next)
{
struct node *tnode;
tnode = (struct node*)malloc(sizeof(*tnode));
if(tnode != NULL)
{
tnode->number = number;
tnode->next = next;
}
return tnode;
}



struct node *mergesort(struct node *head)
{
//head works as temporary node/pointer;
struct node *head_one;
struct node *head_two;


if((head == NULL) || (head->next == NULL))
return head;


head_one = head;
head_two = head->next;                                                                                 //Like exam, traversing an array using 2 pointers(interview question)
while((head_two != NULL) && (head_two->next != NULL))
{
head = head->next;
head_two = head->next->next;
}
head_two = head->next;
head->next = NULL;                     //break list
struct node *temp=merge(mergesort(head_one), mergesort(head_two));
return(temp);
}


struct node *merge(struct node *head_one, struct node *head_two)
{
if(head_one== NULL)
return(head_two);
if(head_two == NULL)
return(head_one);
if(head_two->number > head_one->number)
{
head_one->next= merge(head_one->next,head_two);
return(head_one);
}
else
{
head_two->next =merge(head_two->next,head_one);
return(head_two);
}
}

[LizR]

Unfortunately this is supposed to be a delphi/pascal forum, not a c/c++ forum.

If you have already made your solution (in pascal I assume) what areas do you feel your solution is weak..