在 C 中拆分链表

Question

>我需要使用链表实现一些分而治之的算法(二叉搜索、合并排序等(。
为此，我需要定义一个将某个列表一分为二的方法，以便它们之间的大小差异最多为 1 个元素。
这是我的结构：

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

L是指向linked_list的指针。

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

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

但是，当您在 main 上运行该函数时，它不会按预期工作。

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("%dn", x);  // Will print 0
int* p = NULL;
bar(p);
printf("%pn", (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("%dn", x);  // Will print 55
int* p = NULL;
bar(&p);                  // Notice the & operator
printf("%pn", (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

顺便说一句：

它是基于意见的，但指针的类型定义通常不是一个好主意。