反轉連結串列

你也可以遞迴執行此任務，但我在此示例中選擇使用迭代方法。如果要在連結列表的開頭插入所有節點，則此任務很有用。這是一個例子：

#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）中。