Partition a Linked List (C)

Question

The problem asks us to split a Linked List based on a pivot value (1->2->4->6->3->5 pivot = 5 ) => ( 1->2->4->3->5->6) My Solution to the problem was to create 3 new linked list and split based on the pivot value. However I am not able to concatenate the 3 linked list together and let head point to the new concatenated linked list. Please guide me through on how I can concatenate the 3 linked list and let head point to the concatenated linked list.

void triPartition(ListNode** head, int pivot){

ListNode *cur;
ListNode ** Small = NULL;
ListNode ** Equal = NULL;
ListNode ** Large = NULL;

int Scount = 0 , Ecount = 0 , Lcount = 0;

cur = (*head);

if(cur == NULL)
{
    return 0;
}
if(cur->next == NULL)
{
    return 0;
}

while(cur != NULL)
{
    if(cur->item == pivot)
    {
        insertNode(&Equal, Ecount, cur->item);
        Ecount++;
    }
    else if(cur->item < pivot)
    {
        insertNode(&Small, Scount, cur->item);
        Scount++;
    }
    else
    {
        insertNode(&Large, Lcount, cur->item);
        Lcount++;
    }
    cur = cur->next;
}

This part of my solution does not work

*head = Small;

while((*Small)->next!=NULL)
{
    Small = (*Small)->next;
}
(*Small)->next = Equal;
while((*Equal)->next!=NULL)
{
    Equal = (*Equal)->next;
}
(*Equal)->next = Large;

}

Answer 1

It seems that no professional programmer are going tp help you. So we beginners should help each other ourselves.:)

Using your approach to the function implementation by means of creating at first three separate lists and then combining them in one list I can suggest the following function definition shown in the demonstration program below.

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

typedef struct ListNode
{
    int item;
    struct ListNode *next;
} ListNode;

void clear( ListNode **head )
{
    while (*head)
    {
        ListNode *current = *head;
        *head = ( *head )->next;
        free( current );
    }
}

size_t assign( ListNode **head, const int a[], size_t n )
{
    clear( head );

    size_t i = 0;

    for ( ; i != n && ( *head = malloc( sizeof( ListNode ) ) ) != NULL; i++)
    {
        ( *head )->item = a[i];
        ( *head )->next = NULL;
        head = &( *head )->next;
    }

    return i;
}

FILE *display( const ListNode * const head, FILE *fp )
{
    for ( const ListNode *current = head; current != NULL; current = current->next)
    {
        fprintf( fp, "%d -> ", current->item );
    }

    fputs( "null", fp);
    
    return fp;
}

void triPartition( ListNode **head, int pivot )
{
    ListNode * small = NULL;
    ListNode * equal = NULL;
    ListNode * large = NULL;
    
    ListNode ** small_ptr = &small;
    ListNode ** equal_ptr = &equal;
    ListNode ** large_ptr = &large;

    for ( ListNode *current = *head; current != NULL; )
    {
        ListNode *tmp = current;
        current = current->next;
        tmp->next = NULL;
        
        if ( tmp->item < pivot )
        {
            *small_ptr = tmp;
            small_ptr = &( *small_ptr )->next;
        }
        else if ( pivot < tmp->item )
        {
            *large_ptr = tmp;
            large_ptr = &( *large_ptr )->next;
        }
        else
        {
            *equal_ptr = tmp;
            equal_ptr = &( *equal_ptr )->next;
        }
    }
    
    *equal_ptr = large;
    *small_ptr = equal;
    
    *head = small;
}

int main( void )
{
    int a[] = { 1, 2, 4, 6, 3, 5 };
    ListNode *head = NULL;

    assign( &head, a, sizeof( a ) / sizeof( *a ) );

    fputc( '\n', display( head, stdout ) );
    
    triPartition( &head, 5 );
    
    fputc( '\n', display( head, stdout ) );

    clear( &head );
}

The program output is

1 -> 2 -> 4 -> 6 -> 3 -> 5 -> null
1 -> 2 -> 4 -> 3 -> 5 -> 6 -> null