initialize

9 files changed, 1110 insertions, 0 deletions

diff --git a/c/dataStructure/线性表/线性链表/blist/bhlist.c b/c/dataStructure/线性表/线性链表/blist/bhlist.c
new file mode 100755
index 0000000..1c0dbc8
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/blist/bhlist.c
@@ -0,0 +1,76 @@
+// Implement
+#include "bhlist.h"
+
+void InitList (Blist * L)
+{
+    *L = NULL;
+}
+
+bool AddElem(Blist * L, int e)
+{
+    Blist scan = *L;
+    BNode * new = (BNode *) malloc (sizeof(BNode));
+
+    if (!new)
+    {
+        fprintf(stderr,"Memory error!\n");
+        return false;
+    }
+
+    new->data = e;
+    new->next = NULL;
+
+    if (!scan)
+    {
+        new->prior = NULL;
+        *L = new;
+    }
+    
+    else
+    {
+        while (scan->next)
+            scan = scan->next;
+        new->prior = scan; 
+        scan->next = new;
+    }
+    
+    return true;
+}
+
+void DestroyList (Blist * L)
+{
+    Blist t1 = *L;
+    Blist t2;
+
+    while (t1)
+    {
+        t2 = t1->next;
+        free(t1);
+        t1 = t2;
+    }
+}
+
+void TraverseList(Blist * L)
+{
+    Blist tmp = *L;
+    Blist ta,tb;
+
+    while (tmp)
+    {
+        printf("Element is %d\n",tmp->data);
+        tb = tmp->prior;
+        ta = tmp->next;
+        if (tb)
+            printf("It's prior element is %d, ",tb->data);
+        else
+            printf("No element before it, ");
+        
+        if (ta)
+            printf("and it's next element is %d!\n",ta->data);
+        else
+            printf("No element after it!\n");
+        
+        tmp = tmp->next;
+    }
+    puts("Traverse DONE!");
+}
\ No newline at end of file
diff --git a/c/dataStructure/线性表/线性链表/blist/bhlist.h b/c/dataStructure/线性表/线性链表/blist/bhlist.h
new file mode 100755
index 0000000..659750a
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/blist/bhlist.h
@@ -0,0 +1,23 @@
+#ifndef _BHLIST_H
+#define _BHLIST_H
+
+#include<stdio.h>
+#include<stdbool.h>
+#include<stdlib.h>
+
+typedef struct bnode {
+    int data;
+    struct bnode * prior;
+    struct bnode * next;
+} BNode;
+
+typedef BNode * Blist;
+
+void InitList (Blist * L);
+bool AddElem (Blist * L, int e);
+bool InsertElem (Blist * L, int e, int i);
+bool DeleteElem (Blist * L, int e, int i);
+void DestroyList (Blist * L);
+void TraverseList (Blist * L);
+
+#endif
\ No newline at end of file
diff --git a/c/dataStructure/线性表/线性链表/blist/main.c b/c/dataStructure/线性表/线性链表/blist/main.c
new file mode 100755
index 0000000..09b4247
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/blist/main.c
@@ -0,0 +1,24 @@
+// Driver
+#include "bhlist.h"
+
+int main(void)
+{
+    Blist number;
+
+    int num;
+
+    InitList(&number);
+
+    printf("Please enter number(q to quit): ");
+    while (scanf("%d", &num) == 1)
+        AddElem(&number,num);
+
+    printf("Add element done! Now shows them!\n");
+    printf("%d\n",number->data);
+
+    TraverseList(&number);
+
+    DestroyList(&number);
+
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/线性表/线性链表/hlist.c b/c/dataStructure/线性表/线性链表/hlist.c
new file mode 100755
index 0000000..fc4cf8a
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/hlist.c
@@ -0,0 +1,198 @@
+#include "list.h"
+
+void InitList (List * L)
+{
+    *L = (LNode *) malloc (sizeof(LNode));
+
+    if (!*L)
+    {
+        fprintf(stderr,"Initialization Failed\n");
+        exit(EXIT_FAILURE);
+    }
+
+    (*L)->next = NULL;
+
+    printf("Initialization Successful!\n");
+}
+
+void DestroyList (List * L)
+{
+    // reserve head pointer
+    List T = *L;
+    List tmp;
+
+    if (!T->next)
+        printf("No element in list!\n");
+    else
+    {
+        while (T->next)
+        {
+            tmp = T->next->next;
+            free(T->next);
+            T->next = tmp;
+        }
+
+       if (!T->next)
+           printf("Destroyed list!\n");
+       else
+           printf("Error during destroy list");
+    }
+}
+
+bool AddElem (List * L, ElemType e)
+{
+    List new = *L;
+
+    while (new->next)
+        new = new->next;
+
+    new->next = (LNode *) malloc (sizeof(LNode));
+
+    if (!new)
+        return false;
+    new = new->next;    
+    new->data = e;
+    new->next = NULL;
+
+    return true;
+}
+
+int ListLength (List * L)
+{
+    int count = 0;
+
+    List tmp = *L;
+
+    while (tmp->next)
+    {
+        tmp = tmp->next;
+        count++;
+    }
+    
+    return count;
+}
+
+ElemType GetElem (List * L, int i)
+{
+    List tmp = *L;
+
+    for (int j = 1; j < i; j++)
+            tmp = tmp->next;
+    return tmp->next->data;
+}
+
+int LocateElem (List * L, ElemType e)
+{
+    int i = 1;
+    List tmp = *L;
+
+    while (tmp->next && tmp->next->data != e)
+    {
+        tmp = tmp->next;
+        i++;
+    }
+
+    if (!tmp->next)
+        return 0;
+
+    return i;
+}
+
+ElemType PriorElem(List * L, ElemType e)
+{
+    List tmp = *L;
+    while (tmp->next->data != e)
+        tmp = tmp->next;
+
+    return tmp->data;
+}
+
+ElemType NextElem(List * L, ElemType e)
+{
+    List tmp = *L;
+    while (tmp->next->data != e)
+        tmp = tmp->next;
+    
+    tmp = tmp->next->next;
+
+    return tmp->data;
+}
+
+bool InsertElem (List * L, ElemType e, int i)
+{
+    List scan = *L;
+    List new;
+    int tmp = 1;
+
+    new = (LNode *) malloc (sizeof(LNode));
+
+    if (!new)
+        return false;
+
+    while (scan->next && tmp < i)
+    {
+        scan = scan->next;
+        tmp++;
+    }
+
+
+    if (!scan->next)
+        printf("Reached list end.   Element appended on.\n");
+
+    new->data = e;
+    new->next = scan->next;
+    scan->next = new;
+
+    return true;
+}
+
+bool DeleteElem (List * L, int i)
+{
+    List tmp1 = *L;
+    List tmp2 = tmp1->next;
+
+    for (int j = 1; j < i; j++)
+    {
+            tmp1 = tmp1->next;
+            tmp2 = tmp2->next;
+    }
+
+    if (!tmp2)
+        return false;
+    
+    tmp1->next = tmp2->next;
+    free(tmp2);
+
+    return true;
+}
+
+void TraverseList (List * L)
+{
+    int i = 1;
+    List tmp = (*L)->next;
+
+    if (!tmp)
+        printf("No element could be traversed!\n");
+    else
+    {
+        puts("Traverse list:");
+        while (tmp)
+        {
+            printf("Node %d:\t%d\n",i++,tmp->data);
+            tmp = tmp->next;
+        }
+        puts("Traverse done!\n");
+    }
+}
+
+void OperateMenu (void)
+{
+    puts("List Operation Menu\n");
+    puts("\e[34ma. Add element          b. Initialize list");
+    puts("c. List status          d. Get element from specific position");
+    puts("e. Search element       f. Find prior element");
+    puts("g. Find next element    h. Insert an element");
+    puts("i. Delete an element    j. Traverse list");
+    puts("k. Show Menu            l. Destroy list");
+    puts("q. Quit");
+}
diff --git a/c/dataStructure/线性表/线性链表/hmain.c b/c/dataStructure/线性表/线性链表/hmain.c
new file mode 100755
index 0000000..20aaa92
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/hmain.c
@@ -0,0 +1,207 @@
+#include "list.h"
+
+static void eatline(void)
+{
+    while (getchar() != '\n')
+        continue;
+}
+
+static char get_answer(void)
+{
+    printf("\e[39m\nPlease enter choice > ");
+    return tolower(getchar());
+}
+
+static bool CheckList(bool flag)
+{
+    if (!flag)
+    {
+        printf("List does not exist! Please initialize it!\n");
+        return false;
+    }
+    return true;
+}
+
+int main(void)
+{
+    List L;
+    char ans;
+    ElemType e;
+    int pos;
+    bool flag = false;
+
+    printf("\e[1;1H\e[2J");
+
+    OperateMenu();
+
+    while ((ans = get_answer()) != 'q')
+    {
+        if (strchr("abcdefghijklq",ans) == NULL)
+        {
+            fprintf(stderr,"Please enter choice labeled above!\n");
+            if (ans != '\n')
+                eatline();
+            continue;
+        }
+
+        eatline();
+
+        if (ans == 'k')                     // Show menu
+        {
+            putchar('\n');
+            OperateMenu();
+            continue;
+        }
+
+        if (ans == 'b')                     // Initialize list
+        {
+            InitList(&L);
+            flag = true;
+            continue;
+        }
+
+        if (CheckList(flag) == false)      // Check initialization
+            continue;
+
+        else if (ans == 'l')               // Destroy list
+            DestroyList(&L);
+        
+        else if (ans == 'a')               // Add element
+        {
+            printf("Please enter an number: ");
+            scanf("%d", &e);
+            eatline();
+            if (AddElem(&L, e))
+                printf("Element adding successful!\n");
+            else
+                printf("Element adding failed, please run debug mode!\n");
+        }
+
+        else if (ans == 'c')               // Show list length
+            printf("List contains %d element!\n",ListLength(&L));
+
+        else if (ans == 'd')               // Get element by position
+        {
+            printf("Enter position you want to get: ");
+            scanf("%d",&pos);
+            eatline();
+            int i = ListLength(&L);
+
+            if (pos > i || pos <= 0)
+            {
+                printf("Position error, List now has %i elements!\n", i);
+                continue;
+            }
+
+            printf("Position %d:  %d",pos,GetElem(&L,pos));
+        }
+
+        else if (ans == 'e')             // Get position by element
+        {
+            printf("Enter element value: ");
+            scanf("%d", &e);
+            eatline();
+
+            if ((pos = LocateElem(&L,e)) == 0)
+            {
+                printf("Element %d is not in this list!\n",e);
+                continue;
+            }
+
+            printf("Element position: %d\n",pos);
+        }
+
+        else if (ans == 'f')            // Get prior element
+        {
+            printf("Enter element: ");
+            scanf("%d", &e);
+            eatline();
+
+            if ((pos = LocateElem(&L,e)) == 0)
+            {
+                printf("Element %d is not in this list!\n",e);
+                continue;
+            }
+
+            else if (pos == 1)
+            {
+                printf("First element, no prior element!\n");
+                continue;
+            }
+
+            printf("Prior element of element %d is %d\n",
+                    e,PriorElem(&L,e));
+        }
+
+        else if (ans == 'g')            // Get next element
+        {
+            printf("Enter element: ");
+            scanf("%d", &e);
+            eatline();
+
+            if ((pos = LocateElem(&L,e)) == 0)
+            {
+                printf("Element %d is not in this list!\n",e);
+                continue;
+            }
+
+            else if(pos == ListLength(&L))
+            {
+                printf("Last element, no next element!\n");
+                continue;
+            }
+
+            printf("Next element of element %d is %d\n",
+                    e,NextElem(&L,e));
+        }
+
+        else if (ans == 'h')            // Insert an element
+        {
+            printf("Enter position you want to put: ");
+            scanf("%d", &pos);
+            printf("Enter element you want to add: ");
+            scanf("%d", &e);
+            eatline();
+
+            if (!InsertElem(&L,e,pos))
+            {
+                printf("Insert error!\n");
+                continue;
+            }
+            printf("Insert successful!\n");
+        }
+        
+        else if (ans == 'i')           // Delete an element
+        {
+            int i = ListLength(&L);
+            printf("Enter position you want to delete: ");
+            scanf("%d", &pos);
+            eatline();
+
+            if (pos <= 0)
+            {
+                printf("position should be greater than 0!\n");
+                continue;
+            }
+
+            else if (pos > i || !DeleteElem(&L,pos))
+            {
+                printf("Position error, %d elements in list\n",
+                        i);
+                puts("Delete failed");
+                continue;
+            }
+            puts("Delete successful!");
+        }
+
+        else if (ans == 'j')
+            TraverseList(&L);
+    }
+
+    if (flag)
+        free(L);
+
+    puts("Thanks for using this utility!\n");
+
+    return 0;
+}
diff --git a/c/dataStructure/线性表/线性链表/list.h b/c/dataStructure/线性表/线性链表/list.h
new file mode 100755
index 0000000..1b0e8b0
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/list.h
@@ -0,0 +1,33 @@
+#ifndef _LIST_H
+#define _LIST_H
+
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+#include<ctype.h>
+#include<string.h>
+
+typedef int ElemType;
+
+typedef struct list {
+    ElemType data;
+    struct list * next;
+}LNode;
+
+typedef LNode * List;
+
+void      InitList     (List * L);
+void      DestroyList  (List * L);
+bool      AddElem      (List * L, ElemType e);           // Add an element, length +1
+bool      ListEmpty    (List * L);
+int       ListLength   (List * L);
+ElemType  GetElem      (List * L, int i);                // Get ith element
+int       LocateElem   (List * L, ElemType e);           // return element e's position, if not found, return 0
+ElemType  PriorElem    (List * L, ElemType e);           // return precedent element of e
+ElemType  NextElem     (List * L, ElemType e);           // return element after e
+bool      InsertElem   (List * L, ElemType e, int i);    // insert Elem at i
+bool      DeleteElem   (List * L, int i);                // delete ith element
+void      TraverseList (List * L);                       // traverse all list
+void      OperateMenu  (void);                           // show Menu to user
+
+#endif
\ No newline at end of file
diff --git a/c/dataStructure/线性表/线性链表/nhdriver.c b/c/dataStructure/线性表/线性链表/nhdriver.c
new file mode 100755
index 0000000..86ef056
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/nhdriver.c
@@ -0,0 +1,34 @@
+/* Test driver -- Linked list without head pointer */
+
+#include "list.h"
+
+int main(void)
+{
+    List number;
+
+    InitList(&number);
+
+    for (int i = 0; i < 10; i++)
+        AddElem(&number,i+1);
+
+    TraverseList(&number);
+    printf("%d numbers in list", ListLength(&number));
+
+    putchar('\n');
+
+    InsertElem(&number,7,12);
+    TraverseList(&number);
+ 
+    putchar('\n');
+
+    DeleteElem(&number, 1);
+    TraverseList(&number);
+ 
+    putchar('\n');
+
+    DestroyList(&number);
+
+    TraverseList(&number);
+
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/线性表/线性链表/nhlist.c b/c/dataStructure/线性表/线性链表/nhlist.c
new file mode 100755
index 0000000..d37248d
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/nhlist.c
@@ -0,0 +1,181 @@
+/* Function declaration -- Linked list without head pointer */
+
+#include "list.h"
+
+void InitList(List * L)
+{
+    *L = NULL;
+}
+
+void DestroyList(List * L)
+{
+    List tmp;
+
+    while (*L)
+    {
+        tmp = (*L)->next;
+        free(*L);
+        *L = tmp;
+    }
+}
+
+bool AddElem(List * L, ElemType e)
+{
+    List scan = *L;
+    
+    List new = (LNode *) malloc (sizeof(LNode));
+
+    if (!new)
+    {
+        fprintf(stderr,"Failed Adding element\n");
+        return false;
+    }
+
+    new->data = e;
+    new->next = NULL;
+
+    if (!*L)
+        *L = new;
+    else
+    {
+        while (scan->next)
+            scan = scan->next;
+        scan->next = new;
+    }
+
+    return true;
+}
+
+bool ListEmpty (List * L)
+{
+    if (!*L)
+        return true;
+    return false;
+}
+
+int ListLength (List * L)
+{
+    List tmp = *L;
+    int count = 0;
+    while (tmp)
+    {
+        tmp = tmp->next;
+        count++;
+    }
+
+    return count;
+}
+
+ElemType GetElem (List * L, int i)
+{
+    int n = ListLength(L);
+    if (i > n)
+    {
+        fprintf(stderr,"Position error, Please restricted between 0 and %d",n);
+        return EOF;
+    }
+    List tmp = *L;
+
+    for (int j = 0; j < i; j++)
+        tmp = tmp->next;
+    
+    if (tmp)
+        return tmp->data;
+    return 0;
+}
+
+void TraverseList (List * L)
+{
+    List tmp = *L;
+
+    while (tmp)
+    {
+        printf("%7d",tmp->data);
+        tmp = tmp->next;
+    }
+    putchar('\n');
+}
+
+bool InsertElem (List * L, ElemType e, int i)
+{
+    bool flag = false;
+    List tmp = *L;
+    List new = (LNode *) malloc (sizeof(LNode));
+
+    int n = ListLength(&tmp);
+
+    if (!new)
+    {
+        fprintf(stderr,"Failed to create new node!\n");
+        return flag;
+    }
+
+    new->data = e;
+
+    if (i < 1)
+        fprintf(stderr,"Invalid position!\n");
+
+    else if (i == 1)
+    {
+        new->next = tmp;
+        *L = new;
+        flag = true;
+    }
+
+    else
+    {
+        for (int j = 2; j < i; j++)
+            if (tmp->next)
+                tmp = tmp->next;
+            else
+                break;
+        
+        if (i > n)
+            printf("List length is %d, append element to last!\n",n);
+
+        new->next = tmp->next;
+        tmp->next = new;
+        flag = true;
+    }
+    return flag;
+}
+
+bool DeleteElem (List * L, int i)
+{
+    List t1 = *L;
+    List t2;
+    bool flag = false;
+    int n = ListLength(&t1);
+
+    if (i < 1)
+        fprintf(stderr, "Position error!\n");
+
+    else if (i == 1)
+    {
+        t2 = t1;
+        *L = t1->next;
+        free(t2);
+        flag = true;
+    }
+
+    else if (i <= n)
+    {
+        for (int j = 2; j < i; j++)
+            if (t1->next)
+                t1 = t1->next;
+            else
+                break;
+                
+        if (t1->next)
+        {
+            t2 = t1->next;
+            t1->next = t2->next;
+            free(t2);
+            flag = true;
+        }
+    }
+
+    else
+        printf("No element at position %d\n",i);
+    return flag;
+}
\ No newline at end of file
diff --git a/c/dataStructure/线性表/线性链表/operation.c b/c/dataStructure/线性表/线性链表/operation.c
new file mode 100755
index 0000000..c0dc934
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/operation.c
@@ -0,0 +1,334 @@
+/* Operation based on pointer with head */
+#include "list.h"
+
+void append(List * A, List * B);             // Append B's elements to A
+List ordered_merge(List * A, List * B);     // Merge B's elements to A orderedly
+void overlap(List * A, List * B);
+void ANotB(List * A, List * B);
+void split(List * A, List * B, List * C);
+void reverse(List * A);
+
+// Driver
+int main(void)
+{
+    // This comment is use for test reverse function
+    ///*
+    List a;
+    InitList(&a);
+
+    int d1[] = {1,2,3,4,5,6,7,8,9,10};
+
+    for (int i = 0; i < sizeof(d1)/sizeof(int); i++)
+        AddElem(&a,*(d1+i));
+
+    TraverseList(&a);
+
+    reverse(&a);
+
+    TraverseList(&a);
+
+    DestroyList(&a);
+
+    return 0;
+    //*/
+
+    // This comment is use for test split function
+    /*
+    ElemType d1[] = {-3,9,-5,1,3,6,-13,0,0,-44,42,123,453,12,42,-312,-1324};
+
+    InitList(&a);
+    for (int i = 0; i < sizeof(d1)/sizeof(int); i++)
+        AddElem(&a,d1[i]);
+
+    TraverseList(&a);
+
+    split(&a,&b,&c);
+    TraverseList(&b);
+    TraverseList(&c);
+
+    DestroyList(&b);
+    DestroyList(&c);
+
+    free(a);
+
+    return 0;
+    */
+
+    // This comment is use for test function takes 2 arguments
+    /*
+    ElemType d1[] = {11,22,33,44,99};
+    ElemType d2[] = {44,55,66,77,88};
+
+    // Initialize list
+    InitList(&a);
+    InitList(&b);
+
+    for (int i = 0; i < sizeof(d1)/sizeof(int); i++)
+        AddElem(&a,d1[i]);
+    
+    for (int i = 0; i < sizeof(d2)/sizeof(int); i++)
+        AddElem(&b,d2[i]);
+
+    TraverseList(&a);
+    TraverseList(&b);
+
+    
+    // Check initialization
+    overlap(&a,&b);
+
+    TraverseList(&a);
+
+    // Release list
+    DestroyList(&a);
+    free(a);
+
+    return 0;
+    */
+}
+
+// ------------------------------------------ list with head -----------------------------------------
+void append(List * A, List * B)
+{
+    // Create a new pointer to point A;
+    List C = *A;
+
+    // Get next pointer until hits NULL pointer
+    while (C->next)
+        C = C->next;
+    
+    // Attach last NULL pointer to first element of B
+    C->next = (*B)->next;
+
+    // Release B's head
+    free(*B);
+
+    // Now A has both A and B's elements
+}
+
+List ordered_merge(List * A, List * B)
+{
+    List T1, T2;
+    // For convenience, T1 is smallest one
+    if ((*A)->next->data <= (*B)->next->data)
+    {
+        T1 = *A;
+        T2 = *B;
+    }
+    else
+    {
+        T1 = *B;
+        T2 = *A;
+    }
+
+    // To keep T1 still
+    List T4 = T1;
+
+    // Store next pointer of bigger one
+    List T3;
+
+    /* Both start from Head pointer. So T->next is the real data
+     * we manipulate. Assume T->next is P
+     *
+     * If P1->data <= P2->data:
+     * We use P3 to store P2->next,
+     * attach P2->next with P4,
+     * and attach P2 to P4.
+     * This process will still P1 and move P2 to next
+     * as long as condition remains true.
+     * 
+     * Else, if P1->data > P2->data
+     * Then we move P1 to next to compare with P2 */
+    while (T4->next && T2->next)
+    {
+        if (T4->next->data >= T2->next->data)
+        {
+            T3 = T2->next->next;
+            T2->next->next = T4->next;
+            T4->next = T2->next;
+            T2->next = T3;
+        }
+        else
+            T4 = T4->next;
+    }
+
+    /* Due to every elements are ordered.
+     * so if smaller one runs out,
+     * we only need to append bigger one to it.
+     *
+     * If bigger one runs out, We won't do anything. */
+    if (!T4->next)
+    {
+        T4->next = T2->next;
+        T2->next = NULL;
+
+    }
+
+    // Clear empty list
+    if (!(*A)->next)
+        free(*A);
+    else
+        free(*B);
+    
+    return T1;
+}
+
+void overlap (List * A, List * B)
+{
+    /* If A > B,    release B, moving B to next
+       If B > A,    release A, moving A to next
+       If A = B,    release B, moving A&B to next */
+    List a = *A, b = *B, c;
+
+    while (a->next && b->next)
+    {
+        if (a->next->data > b->next->data)
+        {
+            c = b->next->next;
+            free(b->next);
+            b->next = c;
+        }
+        else if (a->next->data < b->next->data)
+        {
+            c = a->next->next;
+            free(a->next);
+            a->next = c;
+        }
+        else
+        {
+            a = a->next;
+            c = b->next->next;
+            free(b->next);
+            b->next = c;
+        }
+    }
+
+    if (a->next)
+    {
+        c = a->next->next;
+        free(a->next);
+        a->next = c;
+    }
+    else if (b->next)
+    {
+        c = b->next->next;
+        free(b->next);
+        b->next = c;
+    }
+    free(b);
+}
+
+// Get elements appear only in A
+void ANotB (List * A, List * B)
+{
+    /* If A > B, then release B, moving to next
+     * If A < B, moving A till A == B or A > B
+     * If A = B, Release B, moving both A and B
+     */
+    List t1 = *A, t2 = *B;
+    List tmp;
+
+    while (t1->next && t2->next)
+    {
+        if (t1->next->data > t2->next->data)
+        {
+            tmp = t2->next->next;
+            free(t2->next);
+            t2->next = tmp;
+        }
+
+        else if (t1->next->data == t2->next->data)
+        {
+            tmp = t2->next->next;
+            free(t2->next);
+            t2->next = tmp;
+
+            tmp = t1->next->next;
+            free(t1->next);
+            t1->next = tmp;
+        }
+        else
+            t1 = t1->next;
+    }
+
+    while (t2)
+    {
+        tmp = t2->next;
+        free(t2);
+        t2 = tmp;
+    }
+}
+
+void split(List * A, List * B, List * C)
+{
+    /*  if A < 0
+     *      if !B
+     *          B get A node
+     *      else
+     *          bp get A node
+     *  else A > 0
+     *      same as B
+     *  else A == 0
+     *      release A node, move A to A->next
+     */
+    List b, c, tmp, bp, cp, op;
+    tmp = (*A)->next;
+    *B = NULL;
+    *C = NULL;
+
+    while (tmp)
+        if (tmp->data < 0)
+            if (!*B)
+            {
+                *B = tmp;
+                tmp = tmp->next;
+                (*B)->next = NULL;
+                bp = *B;
+            }
+            else
+            {
+                bp->next = tmp;
+                tmp = tmp->next;
+                b = bp->next;
+                b->next = NULL;
+                bp = bp->next;
+            }
+        else if (tmp->data > 0)
+            if (!*C)
+            {
+                *C = tmp;
+                tmp = tmp->next;
+                (*C)->next = NULL;
+                cp = *C;
+            }
+            else
+            {
+                cp->next = tmp;
+                tmp = tmp->next;
+                c = cp->next;
+                c->next = NULL;
+                cp = cp->next;
+            }
+        else
+        {
+            op = tmp;
+            tmp = tmp->next;
+            free(op);
+        }
+}
+// ------------------------------------------ list with head -----------------------------------------
+
+// this function will take list without head
+void reverse(List * A)
+{
+    List prior = NULL, current;
+
+    while (*A)
+    {
+        current = *A;
+        *A = (*A)->next;
+        current->next = prior;
+        prior = current;
+    }
+
+    *A = current;
+}
\ No newline at end of file