Sortering af linket liste

At sortere en linket liste er aldrig helt simpelt. Den letteste måde er at fjerne elementer fra listen, en af gangen, og indsætte dem i en ny sorteret liste og så bytte de to lister til slut.

Jeg har et eksempel her:
http://home20.inet.tele.dk/midgaard/snip/linklist.html
Måske kan det give en ide til hvordan man kan gøre.

jeg lavede engang det her eksempel:

#include <stdio.h>
#include <stdlib.h>

struct node
{
  char *name;
  int val;
  struct node *next;
  struct node *prev;
};

struct node *first2last(struct node *first)
{
    struct node *last;
    last = first;
    if(last!=NULL) while(last->next!=NULL) last=last->next;
    return last;
}

void add(struct node **first, char *name, int val)
{
    struct node *extra,*last;
    extra = (struct node *)malloc(sizeof(struct node));
    extra->name = name;
    extra->val = val;
    extra->next = NULL;
    if(*first==NULL)
    {
        *first = extra;
        extra->prev = NULL;
    }
    else
    {
        last = *first;
        while(last->next!=NULL) last=last->next;
        last->next = extra;
        extra->prev = last;
    }
}

void print(struct node *first)
{
    struct node *curr;
    printf("----------------\n");
    curr = first;
    while(curr!=NULL)
    {
        printf("%s %d\n",curr->name,curr->val);
        curr = curr->next;
    }
    printf("----------------\n");
}

void print2(struct node *last)
{
    struct node *curr;
    printf("----------------\n");
    curr = last;
    while(curr!=NULL)
    {
        printf("%s %d\n",curr->name,curr->val);
        curr = curr->prev;
    }
    printf("----------------\n");
}

void sort(struct node **first)
{
    struct node *p1,*p2,*pp1,*pp2,*temp;
    p1 = *first;
    pp1 = NULL;
    while(p1!=NULL)
    {
        pp2 = p1;
        p2 = p1->next;
        while(p2!=NULL)
        {
            if(p2->val < p1->val)
            {
                /* swap pointers */
                temp = p2;
                p2 = p1;
                p1 = temp;
                /* update next and prev pointers */
                if(p2->next!=p1)
                {
                    temp = p2->next;
                    p2->next = p1->next;
                    if(p1->next!=NULL)
                    {
                        p1->next->prev = p2;
                    }
                    p1->next = temp;
                    if(temp!=NULL)
                    {
                        temp->prev = p1;
                    }
                    pp2->next = p2;
                    p2->prev = pp2;
                }
                else
                {
                    p2->next = p1->next;
                    if(p1->next!=NULL)
                    {
                        p1->next->prev = p2;
                    }
                    p1->next = p2;
                    p2->prev = p1;
                }
                if(pp1==NULL)
                {
                    *first = p1;
                    p1->prev = NULL;
                }
                else
                {
                    pp1->next = p1;
                    p1->prev = pp1;
                }
            }
            pp2 = p2;
            p2 = p2->next;
        }
        pp1 = p1;
        p1 = p1->next;
    }
}

int main()
{
  struct node *first = NULL;
  add(&first, "a", 111);
  add(&first, "bb", 22);
  add(&first, "ccc", 3);
  printf("usorteret:\n");
  print(first);
  printf("usorteret (omvendt):\n");
  print2(first2last(first));
  sort(&first);
  printf("sorteret:\n");
  print(first);
  printf("sorteret (omvendt):\n");
  print2(first2last(first));
  add(&first, "d", 4);
  add(&first, "e", 5);
  printf("usorteret:\n");
  print(first);
  printf("usorteret (omvendt):\n");
  print2(first2last(first));
  sort(&first);
  printf("sorteret:\n");
  print(first);
  printf("sorteret (omvendt):\n");
  print2(first2last(first));
  return 0;
}

De ser begge ud til at løse opgaven :)

Hvis I smider et svar hver, så får I jeres point.

kommer her

Jeg samler ikke på point.