Linked List (5)

Sort a Linked List so that its items are arranged from small to large

void Sort1(Node **head)
{
    if (head == NULL)
        return;
 
    int i, j, n, temp, swap_time;
    Node *p1, *p2;
    n = Length1(*head);                // Bubble Sort: need to know length
 
    for (i = 1; i <= n - 1 && swap_time; i++) {              // if swap_time == 0, break and return
        p1 = *head;                          // start to swap from the beginning of the linked list
        p2 = (*head)->next;
 
        for (j = 1, swap_time = 0; j <= n - i; j++) {
            if (p1->data > p2->data) {                  // if p1 > p2 then swap, if p1 = p2 don't swap -> stable
                temp = p2->data;
                p2->data = p1->data;
                p1->data = temp;
                swap_time++;             // count swap time
            }
            p1 = p1->next;
            p2 = p2->next;
        }
    }
}
 
Node* Sort2(Node *head)
{
    Node *p1 = head;
    int cnt = 0, i, j, tmp, swap_time;
    while (p1 != NULL) {
        cnt++;
        p1 = p1->next;
    }
    for (i = 1; i < cnt; i++) {
        p1 = head;
        swap_time = 0;
        for (j = 0; j < cnt - i; j++) {
            if (p1->data > p1->next->data) {
                tmp = p1->data;
                p1->data = p1->next->data;
                p1->next->data = tmp;
                swap_time++;
            }
            p1 = p1->next;
        }
        if (!swap_time)
            break;
    }
    return head;
}

Merge 2 Linked Lists into 1, and so that its items are arranged from small to large
Node* Merge(Node *h1, Node *h2)
{
    Node *new, *p1, *p2, *p3;
    if ((new = (Node*)malloc(sizeof(Node))) == NULL) {
        printf("fail to allocate memory\n");
        return NULL;
    }
    p1 = h1; p2 = h2; p3 = new;
    while (p1 != NULL && p2 != NULL) {
        if (p1->data <= p2->data) {
            p3->next = p1;
            p1 = p1->next;
        }
        else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }
    if (p1 == NULL)
        p3->next = p2;
    else
        p3->next = p1;
 
    p3 = new->next;
    free(new);
    return p3;
}

Split 1 Linked List to 2, so that all items which are larger than "pivot" go to L1, and all items which are smaller than "pivot" go to L2
void split(node *head, int pivot, node** lt, node** gt)
{
    if (head == NULL)
        return;
 
    node *p1, *p2, *p3;
    p1 = head;
    *lt = (node*)malloc(sizeof(node));
    *gt = (node*)malloc(sizeof(node));
    p2 = lt;
    p3 = gt;
 
    while (p1 != NULL) {
        if (p1->value <= pivot) {
            p2->next = p1;
            p2 = p2->next;
        }
        else {
            p3->next = p1;
            p3 = p3->next;
        }
        p1 = p1->next;
    }
 
    p2->next = NULL;
    p3->next = NULL;
 
    p2 = *lt;
    p3 = *gt;
    *lt = *lt->next;
    *gt = *gt->next;
 
    free(p2);
    free(p3);
}