在一定条件下将节点从一个链表移动到另一个链表

Question

我有一个问题被困了几天，我需要一些帮助。

我有一个名为

splitList

的函数。仅当前一个节点和下一个节点小于当前节点时，该函数才需要从原始列表中删除节点并将其移动到新列表。

一些注意事项：

• 如果第一个节点被删除，指向原始列表的指针可能会改变
• 如果第一个节点大于下一个节点，则从原始列表中删除并移动到新列表
• 如果最后一个节点大于前一个节点，则从原始列表中删除并移动到新列表
• 如果原始列表中只有一个节点被删除并移动到新列表
• 原始列表可以为空

例如：

原列表：3->6->1->9->8->4->5

删除节点的新列表：3->1->8->4

删除后原列表：6->9->5

现在我有几个必须实现和使用的函数，这是我到目前为止所做的：

int deleteFirst(list** lst) // I dont have to use the returned value, but i must return 0 if the list is empty and else 1
{
    // your code:
    list* delNode = *lst;
    if (delNode == NULL)
    {
        printf("List is empty...\n");
        return 0;
    }
    else
    {
        *lst = (*lst)->next;
        delNode->next = NULL;
    }
    return 1;
}

int deleteAfter(list* curr) // same her dont have to use the returned value, but need to return 0 if curr null or point to the last node and else 1
{
    // your code:
    if (curr == NULL)
    {
        return 0;
    }
    else
    {
        list* delItem = curr->next;
        curr->next = delItem->next;
        delItem->next = NULL; 
    }
    return 1;
}

void freeList(list** lst)
{
    // your code:
    while (*lst)
    {
        deleteFirst(lst);
    }
}

现在这是

splitList

函数，也是我陷入困境的地方。我尝试使用两个指针，

prev

和

curr

。问题是，如果节点被删除，我无法找到如何将节点重新连接到新列表。也许我不需要真正删除节点而只需移动它们？

int splitList(list** lst, list** new)
{
    // your code:
    int counter = 0;
    list* prev, * curr, * currNew;

    // If the original is empty
    if (*lst == NULL)
    {
        printf("Original list is empty...\n");
        return counter;
    }

    prev = NULL;
    curr = *lst;

    while (curr->next != NULL)
    {
        if (prev == NULL && curr->data > curr->next->data) // If the first element larger than the next element
        {
            deleteFirst(lst);

            if (*new == NULL) // If the new list is empty
            {
                *new = curr;
            }
            else {
                currNew = *new;

                while (currNew->next != NULL)
                {
                    currNew = currNew->next;
                }
                currNew->next = curr;
            }

        }
    }


}

Answer 1

对于像你我这样的初学者来说，这项任务并不容易。 然而，我们初学者应该互相帮助。:)

对于初学者来说，函数

splitList

具有返回类型

int

int splitList(list** lst, list** new)

但什么也不返回。

其次，该函数不应发出任何消息。

// If the original is empty
if (*lst == NULL)
{
    printf("Original list is empty...\n");
    return counter;
}

函数的调用者将决定是否输出消息。在调用该函数之前，调用者可以检查源列表是否为空。所以上面的 if 语句应该从函数中删除。

while 语句中的条件

while (curr->next != NULL)

与所说的任务描述相矛盾

如果原始列表中只有一个节点被删除并移动到新的节点 列表

这个 if 语句

 if (prev == NULL && curr->data > curr->next->data) 

与任务描述中的另一个要求相矛盾

该函数需要从原始列表中删除节点并移动它 仅当前一个节点和下一个节点较小时才到新列表 比当前节点。

函数的调用

deleteFirst

deleteFirst(lst);

没有什么意义，因为它只是释放了应该移动的节点占用的内存。

这个 while 循环

currNew = *new;

while (currNew->next != NULL)
{
    currNew = currNew->next;
}

效率低下。

移动节点的下一个数据成员应设置为

NULL

。

我可以建议下面的演示程序中所示的以下功能实现。

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

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

void clear( list **lst )
{
    while (*lst)
    {
        list *current = *lst;
        *lst = ( *lst )->next;
        free( current );
    }
}

size_t assign( list **lst, const int a[], size_t n )
{
    clear( lst );

    size_t count = 0;

    while (n-- && ( *lst = malloc( sizeof( list ) ) ) != NULL)
    {
        ( *lst )->data = *a++;
        ( *lst )->next = NULL;

        lst = &( *lst )->next;

        ++count;
    }

    return count;
}

FILE *display( const list *lst, FILE *fp )
{
    for (; lst != NULL; lst = lst->next)
    {
        fprintf( fp, "%d -> ", lst->data );
    }

    fputs( "null", fp );

    return fp;
}

size_t splitList( list **lst1, list **lst2 )
{
    size_t count = 0;

    if (*lst1 != NULL)
    {
        while (*lst2) lst2 = &( *lst2 )->next;

        for (list *prev = NULL; *lst1 != NULL; )
        {
            if (( prev == NULL || prev->data < ( *lst1 )->data ) &&
                ( ( *lst1 )->next == NULL || ( *lst1 )->next->data < ( *lst1 )->data ))
            {
                list *moved = *lst1;

                *lst1 = ( *lst1 )->next;

                moved->next = NULL;

                *lst2 = moved;

                lst2 = &( *lst2 )->next;

                ++count;
            }

            prev = *lst1;

            if (*lst1 != NULL) lst1 = &( *lst1 )->next;
        }
    }

    return count;
}

int main( void )
{
    const int a[] = { 3, 6, 1, 9, 8, 4, 5 };

    list *lst1 = NULL;

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

    fputc( '\n', display( lst1, stdout ) );

    list *lst2 = NULL;

    splitList( &lst1, &lst2 );

    fputc( '\n', display( lst1, stdout ) );
    fputc( '\n', display( lst2, stdout ) );

    clear( &lst1 );
    clear( &lst2 );
}

程序输出为

3 -> 6 -> 1 -> 9 -> 8 -> 4 -> 5 -> null
3 -> 1 -> 8 -> 4 -> null
6 -> 9 -> 5 -> null