反转链表

你也可以递归执行此任务，但我在此示例中选择使用迭代方法。如果要在链接列表的开头插入所有节点，则此任务很有用。这是一个例子：

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

#define NUM_ITEMS 10

struct Node {
  int data;
  struct Node *next;
};

void insert_node(struct Node **headNode, int nodeValue, int position);
void print_list(struct Node *headNode);
void reverse_list(struct Node **headNode);

int main(void) {
  int i;
  struct Node *head = NULL;

  for(i = 1; i <= NUM_ITEMS; i++) {
    insert_node(&head, i, i);
  }
  print_list(head);

  printf("I will now reverse the linked list\n");
  reverse_list(&head);
  print_list(head);
  return 0;
}

void print_list(struct Node *headNode) {
  struct Node *iterator;

  for(iterator = headNode; iterator != NULL; iterator = iterator->next) {
    printf("Value: %d\n", iterator->data);
  }
}

void insert_node(struct Node **headNode, int nodeValue, int position) {
  int i;
  struct Node *currentNode = (struct Node *)malloc(sizeof(struct Node));
  struct Node *nodeBeforePosition = *headNode;

  currentNode->data = nodeValue;

  if(position == 1) {
    currentNode->next = *headNode;
    *headNode = currentNode;
    return;
  }

  for (i = 0; i < position - 2; i++) {
    nodeBeforePosition = nodeBeforePosition->next;
  }

  currentNode->next = nodeBeforePosition->next;
  nodeBeforePosition->next = currentNode;
}

void reverse_list(struct Node **headNode) {
  struct Node *iterator = *headNode;
  struct Node *previousNode = NULL;
  struct Node *nextNode = NULL;

  while (iterator != NULL) {
    nextNode = iterator->next;
    iterator->next = previousNode;
    previousNode = iterator;
    iterator = nextNode;
  }

  /* Iterator will be NULL by the end, so the last node will be stored in
  previousNode.  We will set the last node to be the headNode */
  *headNode = previousNode;
}

反向列表方法的说明

我们以 NULL 开始 previousNode，因为我们知道在循环的第一次迭代中，如果我们在第一个头节点之前寻找节点，它将是 NULL。第一个节点将成为列表中的最后一个节点，下一个变量自然应该是 NULL。

基本上，这里反转链表的概念是我们实际上反转链接本身。每个节点的下一个成员将成为它之前的节点，如下所示：

Head -> 1 -> 2 -> 3 -> 4 -> 5

每个数字代表一个节点。这个清单将成为：

1 <- 2 <- 3 <- 4 <- 5 <- Head

最后，头应该指向第 5 个节点，每个节点应该指向它之前的节点。

节点 1 应该指向 NULL，因为之前没有任何东西。节点 2 应指向节点 1，节点 3 应指向节点 2，等等。

但是，这种方法存在一个小问题。如果我们中断到下一个节点的链接并将其更改为上一个节点，我们将无法遍历列表中的下一个节点，因为它的链接已消失。

这个问题的解决方案是在更改链接之前简单地将下一个元素存储在变量（nextNode）中。