MergeSort and Reverse for Link List

[Peter_APIIT]

Hello all expert programmer, i looking for an algorithm to sort a link list. I found out that merge sort is best suitable in link list.

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

This link demonstrate the algorithm but i really don't understand what it does.

Another problem is i want to reverse a double link list.

I try it with swap head and tail node and traversal to the next node.

struct LList* ReverseSwapNode(struct LList* myList,
struct node *front,
struct node *behind)
{
struct node *dummy;

if (myList != NULL)
{
dummy = (struct node *)malloc(sizeof(struct node));
assert(dummy != NULL);
dummy = front;
front = behind;
behind = dummy;
}
else
{
exit(0);
}

if (front->previous == NULL && behind->next == NULL)
{
behind->previous = NULL;
front->next = NULL;
}
else
{
}

free(dummy);

return myList;
}
// ------------------------------------------------------

A billion thanks for your help.

Your help is greatly appreciated by me and others.

[Peter_APIIT]

Besides that, i also need an algorithm(function) called InsertSorted where insert a node in a correct place. It is non decreasing order.

How to do that ?

I not asking you all do for me but algorithm is good enough.

[Peter_APIIT]

Another try for reverse list is as below:

// ------------------------------------------------------
struct LList* ReverseList(struct LList *myList)
{
struct node *dummy, *traversal, *tmp_head;

/* Algorithm Description

Reverse single LL
Node *Reverse (Node *p)
{
Node *pr = NULL;
while (p != NULL)
{
Node *tmp = p->next;
p->next = pr;
pr = p;
p = tmp;
}
return pr;
}

Swap head and tail, and next head
and previous tail

if its a doubly linked list then just
swap the prev and next pointers for each node and make the current tail as head.
else ricki'sanswer would be fine
*/

if (myList != NULL)
{
traversal = myList->head;
dummy = myList->head;
tmp_head = myList->head;

while(traversal != NULL)
{
dummy->previous = traversal->previous;
traversal->previous = traversal->next;
traversal->next = dummy->previous;

traversal = traversal->next;
}

tmp_head = myList->head;
myList->head = myList->tail;
myList->tail = tmp_head;
}
else
{
exit(0);
}

return myList;
}
// ------------------------------------------------------

This function only display the a single node which tail before reverse.

What wrong with it ?

A billion thanks for your help.

[Peter_APIIT]

The reverse has been solve by me. Below is my code :

// ------------------------------------------------------
struct LList* ReverseList(struct LList *myList)
{
struct node *dummy, *traversal_before, *traversal, *tmp_head;

/* Algorithm Description

Reverse single LL
Node *Reverse (Node *p)
{
Node *pr = NULL;
while (p != NULL)
{
Node *tmp = p->next;
p->next = pr;
pr = p;
p = tmp;
}
return pr;
}

Swap head and tail, and next head
and previous tail

if its a doubly linked list then just
swap the prev and next pointers for each node and make the current tail as head.
else ricki'sanswer would be fine
*/

if (myList != NULL)
{
traversal_before = myList->head;
traversal = myList->head;
dummy = myList->head;
tmp_head = myList->head;

while(traversal != NULL)
{
traversal = traversal->next;

dummy = traversal_before->previous;
traversal_before->previous = traversal_before->next;
traversal_before->next = dummy;

traversal_before = traversal;
}
tmp_head = myList->head;
myList->head = myList->tail;
myList->tail = tmp_head;
}
else
{
exit(0);
}

return myList;
}
// ------------------------------------------------------

Now, the problem is mergesort and InsertSort.

A billion thanks for your help.

[KRUNCH]

well i got some sort of pseudocode for insertion algorithm , then you can use it and modify to your needs:
insertionSort(array A)
for i = 1 to length[A]-1 do
value = A[i]
j = i-1
while j >= 0 and A[j] > value do
A[j + 1] = A[j]
j = j-1
A[j+1] = value