在 C 中拆分链表

Question

我需要使用链表实现一些分而治之的算法（二分查找、归并排序等）。
为此，我需要定义一个方法，将某个列表一分为二，使它们之间的大小相差最大为1个元素。
这是我的结构：

typedef struct linked_list *L;
typedef struct linked_list{
    int info;
    L next;
};

L 是指向 linked_list.

的指针

下面的代码是我尝试将给定列表分成前半部分和后半部分的算法。
我想不出一种方法来 return 生成两个列表，所以我传递了两个空列表作为参数。

void split_list(L r, L front, L back){
    L a = r->next;
    L b = r;

    while( a ){
        a = a->next; 
        if ( a->next ){
            a = a->next;
            b = b->next;
        }
    }

    back = b->next;
    front = r;
    b->next = NULL;

}

但是，当您运行主函数时，它不会按预期工作。

L z = NULL;
/ insert some nodes in z /

L x = NULL;
L y = NULL;

split_list(z, x, y);

尝试打印 x 和 y，它们是空的（显然）。
我认为问题在于列表作为参数传递的方式，但我不知道如何解决这个问题。

Answer 1

你有一个经典的C误区。

您正试图通过将 x 传递给函数来更改 main 中的 x，然后更改函数中的相应变量。你不能那样做！

无效方法的简化示例：

void foo(int x)
{
    x = 55;
}

int globalInt = 42;

void bar(int* p)
{
    p = &globalInt;
}

void main(void)
{
    int x = 0;
    foo(x);
    printf("%d\n", x);  // Will print 0

    int* p = NULL;
    bar(p);
    printf("%p\n", (void*)p); // Will print NULL (nil)

    return 0;
}

原因是C通过值（而不是通过引用）传递变量。因此，当您将 x 传递给函数时，您实际上传递了值 0 并且函数知道值 0 来自名为 x 的变量。

因此在您的情况下，main 中的 x 和 y 在函数调用后仍将为 NULL。

要更改 main 中的变量，您需要传递变量的地址。

void foo(int* x)  // Notice the extra *
{
    *x = 55;      // Notice the extra *
}

int globalInt = 42;

void bar(int** p)      // Notice the extra *
{
    *p = &globalInt;   // Notice the extra *
}

void main(void)
{
    int x = 0;
    foo(&x);            // Notice the & operator
    printf("%d\n", x);  // Will print 55

    int* p = NULL;
    bar(&p);                  // Notice the & operator
    printf("%p\n", (void*)p); // Will print address of the global variable

    return 0;
}

一般规则

如果您看到如下 C 代码：

TYPE x = SomeValue;
func(x);

您肯定知道 x 在函数调用后也将具有值 SomeValue 。

关于您的代码

所以在你的情况下你需要：

void split_list(L r, L* front, L* back)

但是，由于您将 front 分配给 r，因此在函数中更改它似乎有些过分，您可以简单地执行以下操作：

L split_list(L r) {...}

并这样称呼它：

L back = split_list(head); // Now head contains first half and back contains second half

顺便说一句：

这是基于意见的，但指针的 typedef 通常不是一个好主意。

在 C 中拆分链表

Split linked list in C

c

linked-list

structured-data