对链表进行分区(C)

Question

问题要求我们根据数据透视值拆分链表(1->2->4->6->3->5枢轴=5(=>(1->2->4->3->5->6(我的解决方案是创建3个新的链表，并根据数据透视值进行拆分。然而，我无法将3个链表连接在一起，并让head指向新的连接链表。请指导我如何连接3个链表，并让head指向连接的链表。

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;
}

我的解决方案的这一部分不起作用

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

}

Answer 1

似乎没有专业的程序员会帮助你。所以我们初学者应该自己互相帮助

使用您的方法来实现功能，首先创建三个单独的列表，然后将它们组合在一个列表中，我可以建议如下演示程序中所示的功能定义。

#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 );
}

程序输出为

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