Linked List

link list

http://www.coders2020.com/how-do-you-sort-a-linked-list-write-a-c-program-to-sort-a-linked-list

void InsertSort(struct node** headRef) {
    struct node* result = NULL; // build the answer here
    struct node* current = *headRef; // iterate over the original list
        struct node* next;
 
       while (current!=NULL) {
             next = current->next; // tricky - note the next pointer before we change it
             SortedInsert(&result, current);
             current = next;
       }
       *headRef = result;
}
 
/ Dummy node strategy for the head end
void SortedInsert2(struct node** headRef, struct node* newNode) {
       struct node dummy;
       struct node* current = &dummy;
       dummy.next = *headRef;
 
       while (current->next!=NULL && current->next->data < newNode->data) {
               current = current->next;
       }
       newNode->next = current->next;
       current->next = newNode;
 
       *headRef = dummy.next;
}
void MergeSort(struct node** headRef) {
  struct node* head = *headRef;
  struct node* a;
  struct node* b;
  // Base case -- length 0 or 1
  if ((head == NULL) || (head->next == NULL)) {
    return;
 }
   FrontBackSplit(head, &a, &b); // Split head into 'a' and 'b' sublists by slow and fast point
                                                 // We could just as well use AlternatingSplit()

   MergeSort(&a); // Recursively sort the sublists
  MergeSort(&b);
  *headRef  = SortedMerge(a, b); // answer = merge the two sorted lists together
}

struct node* SortedMerge3(struct node* a, struct node* b) {
  struct node* result = NULL;
  // Base cases
  if (a==NULL) return(b);
  else if (b==NULL) return(a);

   // Pick either a or b, and recur
   if (a->data <= b->data) {
     result = a;
     result->next = SortedMerge3(a->next, b);
  }
   else {
     result = b;
     result->next = SortedMerge3(a, b->next);
  }
  return(result);
}

sort a linked list

selection sort by swap values

//Assume HEAD pointer denotes the first element in the linked list
// only change the values…don’t have to change the pointers
 
Sort( Node *Head)
{
    node* first,second,temp,min;
    first= Head;
    while(first!=null)
    {
        min = first;
        second=first->NEXT;
        while(second!=null)
        {
            if(min->value > second->value)
                min = second;
            second=second->NEXT;
            }
            if(min!=first)
                swap_value(min,first);
 
        first=first->NEXT;        
    }
}

reverse a linked link:

1)while loop version

void reverse_single_linked_list(struct node** headRef)
    {
      struct node* result = NULL;
      struct node* current = *headRef;
      struct node* next;
      while (current != NULL)
      {
        next = current->next; // tricky: note the next node
        current->next = result; // move the node onto the result
        result = current;
        current = next;
      }
      *headRef = result;
    }

2)recursive version:

void RecursiveReverse(struct node** headRef) {
   struct node* first;
   struct node* rest;
   if (*headRef == NULL) return; // empty list base case
 
   first = *headRef; // suppose first = {1, 2, 3}
   rest = first->next; //         rest = {2, 3}
 
   if (rest == NULL) return; // empty rest base case
 
   RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                                           // after: rest = {3, 2}
 
   first->next->next = first; // put the first elem on the end of the list
   first->next = NULL; // (tricky step -- make a drawing)
 
   *headRef = rest; // fix the head pointer
}

http://www.openasthra.com/c-tidbits/reversing-single-linked-list-recursively/
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License