Quicksort on linked list with helper lists

Question

I need to preform quickSort on linked list, the problem is I can't figure out how to concatenate the small, pivot and big side of the list.

The partition function works, and I am able to divide the list each time until base case.

Couple notes about the question requirements:

• i must split list (example below).
• pivot is always the first element.
• after concatenate the parts the original list's pointer should point to sorted list

for example:

original list: 5->3->7->1->9->8->2->5->6

pivot list: 5->NULL

smaller or equal than the pivot list: 3->1->2->5 (first run ... second .. keep divide until base case)

larger than the pivot list: 7->9->8->6 (first run ... second .. keep divide until base case)

original list after first run: NULL

end result : 1->2->3->5->5->6->7->8->9->NULL

code:

void partition(list **lst, list **pivot, list **small, list **big)
{
    // your code:
    list *curr, *pivotEl, *smallHead, *smallTail, *largeHead, *largeTail;

    pivotEl = *lst;
    curr = (*lst)->next;

    smallHead = smallTail = largeHead = largeTail = NULL;

    while (curr != NULL)
    {
        if (curr->data <= pivotEl->data)
        {
            if (smallHead == NULL)
            {
                smallHead = curr;
                smallTail = curr;
            }
            else
            {
                smallTail->next = curr;
                smallTail = curr;
            }
        }
        else
        {
            if (largeHead == NULL)
            {
                largeHead = curr;
                largeTail = curr;
            }
            else
            {
                largeTail->next = curr;
                largeTail = curr;
            }
        }

        curr = curr->next;
    }

    // Close the links
    pivotEl->next = NULL;

    if (smallTail != NULL) smallTail->next = NULL;
    if (largeTail != NULL) largeTail->next = NULL;

    // connects to the lists
    *pivot = pivotEl;
    *small = smallHead;
    *big = largeHead;
}

void quickSortList(list **lst) // here is i am stuck
{
    // your code:
    list *temp = *lst, *big, *small, *pivot;

    if (temp && temp->next)
    {
        partition(lst, &pivot, &small, &big);
        quickSortList(&small);
        quickSortList(&big);
    } 
    else {
        pivot->next = big;
        if (small) 
        {
          list* cur = small;
          while (cur->next) {
            cur = cur->next;
        }
        cur->next = pivot;
        *lst = small;
    }
    else {
        *lst = pivot;
    }


}

Answer 1

You could define this function which extends a linked list with another one. There is no magic here: you'll have to walk through the first list to find its tail, and then set the tail's next field to the head of the next list. If the first list is empty, then that list's head pointer must be mutated to be come the other list's head:

void concat(list **lst, list *other) {
    if (*lst) {
        list *cur = *lst;
        while (cur->next) {
            cur = cur->next;
        }
        cur->next = other;
    } else {
        *lst = other;
    }
}

Now your quickSortList function can be completed as follows:

        pivot->next = big; // Or: concat(&pivot, big);
        concat(&small, pivot);
        *lst = small;

Note that we can be sure that pivot is a list with exactly one element, so we don't actually need to rely on concat for linking it with big. A simple assignment to its next field does the trick.

Embedded code

In comments you write you "can't use other helper function". I see no reason why you should not employ good practice, but here is the same principle as one code block:

        pivot->next = big;
        if (small) {
            list *cur = small;
            while (cur->next) {
                cur = cur->next;
            }
            cur->next = pivot;
            *lst = small;
        } else {
            *lst = pivot;
        }

All code to run the example

#include <stdio.h>
#include <stdlib.h>

typedef struct list {
    int data;
    struct list *next;
} list;

list * createNode(int data, list *next) {
    list * node = malloc(sizeof(list));
    node->data = data;
    node->next = next;
    return node;
}

void printList(list *lst) {
    while (lst) {
        printf("%d -> ", lst->data);
        lst = lst->next;
    }
    printf("null\n");
}

void partition(list** lst, list** pivot, list** small, list** big)
{
    // your code:
    list* curr, * pivotEl, * smallHead, * smallTail, * largeHead, * largeTail;

    pivotEl = *lst;
    curr = (*lst)->next;

    smallHead = smallTail = largeHead = largeTail = NULL;

    while (curr != NULL)
    {
        if (curr->data <= pivotEl->data)
        {
            if (smallHead == NULL)
            {
                smallHead = curr;
                smallTail = curr;
            }
            else {
                smallTail->next = curr;
                smallTail = curr;
            }
        }
        else {
            if (largeHead == NULL)
            {
                largeHead = curr;
                largeTail = curr;
            }
            else {
                largeTail->next = curr;
                largeTail = curr;
            }
        }

        curr = curr->next;
    }

    // Close the linkes
    pivotEl->next = NULL;

    if(smallTail != NULL) smallTail->next = NULL;
    if(largeTail != NULL) largeTail->next = NULL;

    // connects to the lists
    *pivot = pivotEl;
    *small = smallHead;
    *big = largeHead;

}

void quickSortList(list** lst) // here is i am stuck
{
    // your code:
    list* temp = *lst, * big, * small, * pivot;

    if (temp && temp->next)
    {
        partition(lst, &pivot, &small, &big);
        quickSortList(&small);
        quickSortList(&big);
        pivot->next = big;
        if (small) {
            list *cur = small;
            while (cur->next) {
                cur = cur->next;
            }
            cur->next = pivot;
            *lst = small;
        } else {
            *lst = pivot;
        }
    }
}


int main(void) {
    list *head = createNode(5, 
                 createNode(3,
                 createNode(7,
                 createNode(1,
                 createNode(9,
                 createNode(8,
                 createNode(2,
                 createNode(5,
                 createNode(6, NULL)))))))));
    printList(head);
    quickSortList(&head);
    printList(head);
    return 0;
}

Output:

5 -> 3 -> 7 -> 1 -> 9 -> 8 -> 2 -> 5 -> 6 -> null
1 -> 2 -> 3 -> 5 -> 5 -> 6 -> 7 -> 8 -> 9 -> null