C 中的递归链表反转函数

Question

My List是通过这两个结构实现的。 第一个包含列表中的项，而第二个包含列表本身。

typedef Employee Item;
typedef struct ListNodeTag {
    Item item;
    struct ListNodeTag *next;
} ListNode;
typedef struct {
    int size;
    ListNode *first;
} List;

我正在尝试使用以下递归函数来反转列表的内容，但是，一旦列表中有多个项目，我就会出现分段错误。

void Reverse(List *L){
  ListNode *q,*p;
  q = L->first;
  p = q->next;
  if(p == NULL)
    return;
  Reverse(L);
  q->next->next = q;
  q->next = NULL;}

我认为问题在于，我不是将列表的成员作为函数参数传递，而是传递指向列表本身的指针。 我将如何更改此代码以使其在不传递其他参数的情况下工作？

Answer 1

您需要将另一个参数传递给函数，以将递归函数前进到列表末尾。这可以像这样完成-

void Reverse(ListNode *f, List *l){
    if(l->first == NULL)
        return;
    //Last node reached
    if(f->next==NULL){
        l->first->next = NULL;
        l->first = f;
        return;
    }
    ListNode *p,*q;
    p = f;
    q = f->next;
    Reverse(f->next,l);
    q->next = p;
}

虽然这个函数有效，但它需要大量内存，所以我推荐一种迭代方法，比如这个-

void Reverse(List *l){
    ListNode *f = l->first;
    ListNode *fn,*fnn;
    if(f==NULL)
        return;
    fn = f->next;
    if(fn==NULL)
        return;
    fnn = fn->next;
    while(fnn!=NULL){
        fn->next = f;
        f = fn;
        fn = fnn;
        fnn = fnn->next;
    }
    fn->next = f;
    l->first->next = NULL;
    l->first = fn;
}

Answer 2

在将项目附加到列表时，是否确保初始化所有下一个指向 NULL 的指针？

另外，正如我所读的那样，该函数实际上不会递归，因为您总是传递 L。换句话说，在第一次调用之后，函数如何知道在列表中更进一步？