Linked List
 Table of Contents

#### 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