链表之单链表逆序（反向）

运气真是太好了，两天内的三次笔试居然都考到对单链表进行反向！

要求像这样：对 A -> B -> C 进行单链表反向操作，得到： C -> B -> A

元素的定义如下：

typedef struct Node {
    char data;
    struct Node* next;
} Node;

操作方法总的来说很简单：

1. 遍历链表的每一个节点P；
2. 使节点P的next指向该节点的前面那个节点；

为了使节点P的next指向前面那个节点，所以得定义一个变量来保存前面那个节点。当然，在此之前还要进行一步的操作就是保存P节点的next，以便进行迭代。

具体实现代码可以是这样的：

Node* reverse(Node* root) {
  Node* new_root = NULL;            // 用来保存前面那个节点
  while (root) {                    // 遍历每个节点
    Node* next = root->next;        // 保存下一个节点
    root->next = new_root;          // 重新设置新的节点使其指向前一个节点
    new_root = root;                // 这两句：遍历指针后移
    root = next;
  }
  return new_root;                  // 新的头结点
}

完整的代码：

#include <stdio.h>

typedef struct Node {
  char data;
  struct Node* next;
} Node;

void print_list(Node* root) {
  while (root) {
    printf("%c ", root->data);
    root = root->next;
  }
  printf("\n");
}

Node* reverse(Node* root) {
  Node* new_root = 0;
  while (root) {
    Node* next = root->next;
    root->next = new_root;
    new_root = root;
    root = next;
  }
  return new_root;
}

int main() {
  Node d = { 'd', 0 };
  Node c = { 'c', &d };
  Node b = { 'b', &c };
  Node a = { 'a', &b };

  Node* root = &a;
  print_list(root);
  root = reverse(root);
  print_list(root);

  return 0;
}

参考

• How to reverse a singly linked list using only two pointers?