0

我有以下 C 代码，它返回链表的反向。

虽然它反转了链表，但我从来没有得到反转链表的头部，因为restofElements节点被覆盖了。 

S *reverseRecursive(S *headref) {
    S *firstElement   = NULL;
    S *restOfElements = NULL;

    if (headref==NULL) {
        return ;
    }

    firstElement = headref;
    restOfElements = headref->next;

    if (restOfElements == NULL)
        return headref;   

    reverseRecursive(restOfElements);    
    firstElement->next->next  = firstElement;
    firstElement->next  = NULL;          
    headref = restOfElements; 

    return headref; 
}

如何将反向链表节点的头部返回给调用程序？

4

6 回答 6

1

如果要更改头指针，则必须通过引用（作为指针）传递它。应该修改原型以接收作为 S ** 的头部。

S *reverseRecursive(S **headref);
于 2013-08-23T13:14:53.847 回答
1

反向列表的头部等于反向列表的头部restOfElements（因为原始headref必须成为反向列表的最后一个元素）。所以存储回避调用的结果应该这样做（正如吉姆在他的评论中已经建议的那样）：

...
headref = reverseRecursive(restOfElements);  
firstElement->next->next  = firstElement;
firstElement->next  = NULL;          
/* headref = restOfElements; that's wrong */    
return headref;
于 2013-08-23T13:41:40.923 回答
1

应该更近了。

S *reverseRecursive(S *headref)
 {
  S *firstElement   = NULL;
  S *restOfElements = NULL;
  S *new_head = NULL;
  if (headref==NULL)
    {
    return ;
    }
  firstElement = headref;
  restOfElements = headref->next;
  if (restOfElements == NULL)
       return headref;   
  new_head = reverseRecursive(restOfElements); 
  restOfElements->next = new_head;           
  return restOfElements;
}
于 2013-08-23T13:44:59.197 回答
1

谢谢大家。我对其进行了一些修改，现在可以使用了。让我知道你的意见。new_head 是一个全局变量。

S *reverseRecursive(S *headref)
 {
  S *firstElement   = NULL;
  S *restOfElements = NULL;

  if (headref==NULL)
    {
    return ;
    }
    firstElement = headref;


   if (headref->next == NULL)
      return headref;   
   else
    restOfElements = headref->next;


   reverseRecursive(restOfElements);

   firstElement->next->next  = firstElement;

   firstElement->next  = NULL;          

   if(new_head == NULL ) //just dont take it ervery time
      new_head = restOfElements;

   return new_head; 

  }
于 2013-08-23T14:27:07.243 回答
1

$ gcc -std=c99 -Wall -Wextra reverse.c

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

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

void print_list(S* list) {
  if (list == NULL) { printf("NULL\n"); return; }
  printf("%d ", list->data);
  print_list(list->next);
}

S* reverse_aux(S* list, S* tail) {
  // invalid arg
  if (list == NULL) { return NULL; }

  // base case
  if (list->next == NULL) {
    list->next = tail;
    return list;
  }

  // general case
  S* tmp = list->next;
  list->next = tail;

  return reverse_aux(tmp, list);
}

S* reverse(S* list) { return reverse_aux(list, NULL); }

int main(int argc, char* argv[]) {
  // build a list with which to test
  S a[10];
  for (unsigned i = 0; i < sizeof(a)/sizeof(S); ++i) {
    a[i].data = i;
    a[i].next = &a[i+1];
  }
  a[sizeof(a)/sizeof(S) - 1].next = NULL;
  S* list = &a[0];

  print_list(list);
  list = reverse(list);
  print_list(list);

  return 0;
}

实际上，由于 reverse 是破坏性的（它改变了它的论点），一个更好的界面设计可能是

void reverse(S** plist);
reverse(&list);
于 2013-08-23T14:49:52.767 回答
0

所以有两种方法可以递归地反转列表。

首先，一些设置。让我们可以轻松地加载和打印字符串的链接列表，这样我们就可以确保这些东西有效：

// linked_list.c
#include <stdio.h>
#include <stdlib.h>

// a linked lis of strings
typedef struct S {
  struct S * next;
  char * val;
} S;

// print out the list
void showS(char * const name, S * head) {
  printf("%s: (", name);
  while (head){
    printf(" ");
    printf("%s",head->val);
    head = head->next;
    printf( "%c", head ? ',' : ' ' );
  }
  printf(")\n");
}

// convert an array of strings into a linked list of strings
S * mkS(int n, char ** args) {
  S * head = NULL;

  if (n > 0 && (head = calloc(n, sizeof(S)))){
    S * curr = head - 1;

    while (n-- > 0) {
      curr++;
      curr->val = *args++;
      curr->next = curr + 1;
    }
    curr->next = NULL;
  }

  return head;
}

反转列表的一种方法是在我们找到列表的新头部后将其传回。我们在本地不需要它（因为我们只是将当前元素移动到新的一端），但是我们需要它以便调用者在我们完成后有一个指向列表头部的指针。

// reverse a list one way
S * revS1( S * const head ){
  if (head && head->next) {
    S * const new_head = revS1( head->next );
    head->next->next = head;
    head->next = NULL;
    return new_head;
  } else {
    return head;
  }
}

另一种方式采用指向指针的指针。唯一的区别是我们不需要返回任何东西，因为我们直接修改了调用者拥有的变量。我更喜欢这种调用方法，因为更清楚的是我们正在修改列表，而不是返回副本。调用者也更难以这种方式意外丢失指向新头的指针。

// reverse a list another way
void revS2( S ** phead ){
  S * const head = *phead;
  if (head && head->next) {
    *phead = head->next;
    revS2( phead );
    head->next->next = head;
    head->next = NULL;
  }
}

但比这两种方法更好的是非递归地反转列表。这些函数都不是尾递归的，因此编译器必须为列表中的每个元素分配新的堆栈帧。尝试反转一个足够长的列表，你会炸掉你的筹码。使用 while 循环来反转列表要好得多。

// reverse a list non-recursively
void revS3( S ** phead ){
  S * head = *phead;
  S * reversed = NULL;

  while (head) {
    S * curr = head;
    head = curr->next;
    curr->next = reversed;
    reversed = curr;
  }
  *phead = reversed;
}

现在我们可以通过在命令行中构建列表来测试我们的结果：

// just use the command line arguments as our list
int main(int argc, char** argv){

  S* list1 = mkS(argc - 1, argv + 1);
  S* list2 = mkS(argc - 1, argv + 1);
  S* list3 = mkS(argc - 1, argv + 1);

  showS( "given", list1 );

  showS( "revS1", revS1(list1) );

  revS2( &list2 );
  showS( "revS2", list2 );

  revS2( &list3 );
  showS( "revS3", list3 );

  return 0;
}

所以让我们编译：

% gcc -Wall linked_list.c -o linked_list

并进行一些试运行

% ./linked_list 
given: ()
revS1: ()
revS2: ()
revS3: ()
% ./linked_list first second third 
given: ( first, second, third )
revS1: ( third, second, first )
revS2: ( third, second, first )
revS3: ( third, second, first )
% ./linked_list only
given: ( only )
revS1: ( only )
revS2: ( only )
revS3: ( only )
于 2013-09-14T05:07:31.397 回答