C-用'from'和'to'索引分割一个单链表

Question

我最近遇到了一些有关按特定位置拆分链表的问题。这是我的必需任务：

写入spitlist功能：

• 将原始列表分为2个子列表。

• splitlist（n1，n2），其中n1是开始位置（从0开始计数），n2是子列表1中的元素数。其余的是sublist2。

我已经完成了一个拆分列表练习，只需要sublist1从0位置开始。这是本练习的代码：

void FrontBackSplit(struct Node* source, struct Node** frontRef, 
                struct Node** backRef)
{
int n; //length of node;

struct Node* current = source;

int pos; scanf("%d", &pos);
//position to split 
for (int i = 0; i < pos; i++)
    current = current->next;


*frontRef = source;
*backRef = current->next;
current->next = NULL;
}

但是我不知道如何解决上述任务。如何将所有剩余节点放入sublist2？请帮助:(

Answer 1

尝试类似的东西：

struct Node* splitlist(struct Node* l, unsigned int n)
{
    for (int i = 0; i < n; ++i)
    {
        if (l == NULL) return NULL;
        l = l->next;
    }
    if (l == NULL) return NULL;

    // Save head of new list
    struct Node* retval = l->next;

    // Break the list apart
    l->next = NULL;

    // return the new list
    return retval;
}

并且这样称呼

struct Node* newList = splitlist(originalList, 42);

Answer 2

您在这里。

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

struct Node
{
    int value;
    struct Node *next;
};

int push_front( struct Node **head, int value )
{
    struct Node *new_node = malloc( sizeof( struct Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->value = value;
        new_node->next = *head;

        *head = new_node;
    }

    return success;
}

void display( const struct Node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->value );
    }

    puts( "null" );
}

struct ListPair
{
    struct Node *head1;
    struct Node *head2;
};


struct ListPair split( struct Node **head, size_t pos, size_t n )
{
    struct ListPair p = { .head1 = NULL, .head2 = NULL };

    struct Node **current1 = &p.head1;
    struct Node **current2 = &p.head2;

    for ( size_t i = 0; *head != NULL && i != pos; i++ )
    {
        *current2 = *head;
        *head = ( *head )->next;
        ( *current2 )->next = NULL;
        current2 = &( *current2 )->next;
    }

    while ( *head != NULL && n-- )
    {
        *current1 = *head;
        *head = ( *head )->next;
        ( *current1 )->next = NULL;
        current1 = &( *current1 )->next;
    }

    while ( *head != NULL )
    {
        *current2 = *head;
        *head = ( *head )->next;
        ( *current2 )->next = NULL;
        current2 = &( *current2 )->next;
    }

    return p;
}


int main(void) 
{
    const size_t N = 15;
    struct Node *head = NULL;

    srand( ( unsigned int )time( NULL ) );  

    for ( size_t i = 0; i < N; i++ )
    {
        push_front( &head, rand() % N );
    }

    display( head );
    putchar( '\n' );

    struct ListPair p = split( &head, N / 3, N / 3  );

    display( head );
    display( p.head1 );
    display( p.head2 );

    return 0;
}

程序输出可能看起来像

7 -> 13 -> 6 -> 8 -> 11 -> 1 -> 3 -> 3 -> 10 -> 8 -> 3 -> 1 -> 2 -> 14 -> 9 -> null

null
1 -> 3 -> 3 -> 10 -> 8 -> null
7 -> 13 -> 6 -> 8 -> 11 -> 3 -> 1 -> 2 -> 14 -> 9 -> null

首先是指针head指向一个列表。

然后此列表分为两个列表p.head1和p.head2。列表p.head1从等于5的位置开始获取原始列表的5个元素。

所有其他元素已移至列表p.head2。

因此，原始列表为空。现在，它的所有元素都分为两个列表p.head1和p.head2。