C - 如何以相反的顺序打印出单向链表

Question

struct node
{
  int info;
  struct node *next;
};
typedef struct node node;
void *printRev(node *head){
      int count=0;
      int i;
      node *beforeFin;
      node *tempHead;
      tempHead = head;
      while(tempHead->next != NULL){
          count++;
          tempHead->next = tempHead->next->next; //LAST ITERATION SHOULD BE AT THE END OF LIST
      }
      printf("COUNT IS: %dn", count);
      for(i = 0; i <= count; i++){
        beforeFin = Prev(head, tempHead->next);
        printf("%d", beforeFin->info);
      }
      printf("n");
    }

截至目前，打印出来：

COUNT IS: 3
Segmentation fault (core dumped)

Prev在给定指针(tempHead->next(之前返回指向节点的指针，我的目的是使用上面的for循环以相反的顺序打印出单向链表。因此，在下面的示例中，给定节点的->info应返回 5(在第一次迭代之后(。

在打印计数的printf之前，tempHead->next应指向最终节点。

现在我正在通过2 3 5 4，这给了我 4 之前的计数。像这样打印出4 5 3 2

我将不胜感激任何帮助，正如您可能知道的那样，我是初学者。提前谢谢大家！

我可以使用递归来做到这一点，但我想学习找出这种方法。

Answer 1

要以相反的顺序打印单个链表，您可以使用递归函数。在离开递归函数之前，您必须单步进入递归到最后并打印列表的元素：

void printReverse(node *act)
{
    if ( act == NULL )          // terminate if end of list is reached
        return;
    printRev( act->next );      // print next node 
    printf( "%d ", act->info ); // print this node
}

如果你不想使用递归，你当然可以反转列表，然后打印列表，最后再次反转。

反转列表并不困难。遍历列表，获取每个元素并将其重新排序到列表的头部前面。

node * reverse(node *head)
{
  node *act, *prev;
  if ( head == NULL )
      return;
  prev = head;
  act = head->next;
  while ( act != NULL )
  {
      prev->next = act->next;
      act->next = head;
      head = act;
      act = prev->next;
  }
  return head;
}
void printReverse(node *head)
{
    node *act;
    act = reverse(head);
    while ( act != NULL )
    {
      printf( "%d ", act->info ); // print this node
      act = act->next;
    }
    reverse(head);
}

Answer 2

由于要避免递归，因此需要先反转列表。我在原始代码中看到了一些尝试，但看起来不正确。请尝试以下操作：

node *current = head;
if (current != NULL) {
    node *prev = NULL;
    for (node *next = current->next; ; next = (current = next)->next) {
        current->next = prev;
        prev = current;
        if (next == NULL)
            break;
    }
}

然后current将指向列表的头部，您可以使用列表上的next链接进行遍历。请注意，它将修改您的原始列表，但这是我理解原始要求的预期。

Answer 3

递归算法的问题在于，如果你像我一样有点偏执，列表可能足够大，导致递归调用汇总并溢出堆栈。如果列表来自某些用户输入，则可用于拒绝服务攻击。因此，我认为有两个合理的选择：

1. 创建列表的反向副本并打印出来。
2. 将列表反转到位，打印出来，可能反转回来。

如果您在内存受限设置或大型列表中工作，后者很有趣。

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
struct node {
  int value;
  struct node * next;
};
void reverse_inplace (struct node ** list) {
  assert(list != NULL);
  struct node * follow = NULL, * lead = *list;
  while (lead != NULL) {
    struct node * next = lead->next;
    lead->next = follow;
    follow = lead;
    lead = next;
  }
  *list = follow;
}
void print (struct node const * head) {
  printf("( ");
  while (head) {
    printf("%d ", head->value);
    head = head->next;
  }
  printf(")");
}
void link (struct node * array, size_t count) {
  struct node * follow = NULL;
  while (count-->0) {
    array[count].next = follow;
    follow = &(array[count]);
  }
}
void fill (struct node * list, int value, int const step) {
  while (list != NULL) {
    list->value = value;
    value += step;
    list = list->next;
  }
}
int main () {
  size_t const sizes[] = {1, 2, 6};
  size_t const num =
    sizeof(sizes) / sizeof(sizes[0]);
  size_t caseId = 0;
  for (; caseId < num; ++caseId) {
    struct node * head =
      malloc(sizeof(*head) * sizes[caseId]);
    printf("Case %zu: List of size %zun",
      caseId, sizes[caseId]);
    link(head, sizes[caseId]);
    fill(head, caseId, caseId);
    printf("  initial: ");
    print(head);
    printf(" n");
    reverse_inplace(& head);
    printf(" reversed: ");
    print (head);
    printf(" n");
    reverse_inplace(& head);
    free(head);
  }
  printf("Case %zu: empty list n", caseId);
  struct node * head = NULL;
  printf("  initial: ");
  print(head);
  printf(" n");
  reverse_inplace(& head);
  printf("  reversed: ");
  print(head);
  printf(" n");
  return 0;
}

(活在 ideone 上(