c - C 中的递归链表反转函数

Question

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

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