implementing shell sort for linked lists?

Question

I'm trying to implement shell sort on singly-linked lists. What I have tried to do is get the respective elements based on the inc value and sort them. However, I'm only familiar with shell sort implementation on arrays and not linked lists. Any help is appreciated.

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

typedef struct node n;

void add(int a);
void shellsort(int size);
void display();
void moveptr(n*a, int distance);

n* head=NULL;

void main()
  { int i,x,size;
    printf("How many elements do you want to enter: ");
    scanf("%d",&size);
    printf("Enter the data: ");
    for(i=0;i<size;i++)
      { scanf("%d",&x);
        add(x);
      }
     
    printf("List currently is: ");
    display();
    shellsort(size);
    printf("\nafter sorting list is: ");
    display();
  }

void add(int a)
  { n *temp = (n*)malloc(sizeof(n));
    temp->data=a;
    temp->next=head;
    head=temp;
  } 

void display()
 { n* temp=head;
   while(temp!=NULL)
     { printf("%d-->",temp->data);
          temp=temp->next;
      }
  }

void moveptr(n *ptr, int distance) // this moves a temp pointer to required location
  { int i=0;
    while(i<distance)
       {
           ptr=ptr->next;
           i=i+1;
       }   
  }

void shellsort(int size)
  { int i,j,temp,inc=size/2;
    n *a=head,*b=head;
    do{
        for(i=0;i<size;i++)
          { 
            for(j=i+inc;j<size;j+=inc)
             { b=head;
               moveptr(b,j);
               if(a->data > b->data)
                 { temp=b->data;
                   b->data=a->data;
                   a->data=temp;
                 }
             }
             a=a->next;
            }
        inc=inc/2;
     }while(inc>=1);
 }

Answer 1

If you insist on using shell sort:

• allocate an array of pointers to list items,
• initialize this array to point to the individual items in the list
• sort the array using shell sort
• relink the list in the order of the array elements
• free the list.