0 是我不懂事了

这玩意儿我在上古时代就写过了，不就是指针断开再链接上嘛！仅一眼，就已经秒了。

可是啊，可是啊，它苦涩如歌... 我已经好几次在面试中遇到反转链表，并且都翻车了！从初见时的心中一喜，到过程中的逐渐怀疑，再到运行报错“null pointer”时的惶恐，最终在百般调试后的绝望... 反转链表杀我！啊！无所不能的C++之神，请赐予我力量吧！

反转链表：“咋，你还反了天了要”？

今天就要将所有反转链表一网打尽！

1 题目

反转整个链表

2 题解

dummy node 就是手动创建的一个节点，指向链表的头。
这个预处理操作，在链表的头会变的场景下很有用，避免了分情况讨论头是否会变的麻烦。
最后 dummy node 的 next 就是链表的头。

2.1 不使用 dummy node - 简单

反转逻辑

维护 3 个指针：pre、cur、next。只要 cur 不为空指针，就一直继续。

断开 cur 和 cur 的后继之前，先 next = cur->next 将后继保存下来；
cur的后继指向 pre，即 cur->next = pre；
更新 pre：pre = cur；
更新 cur：cur = next；

最终 cur 为空指针，pre 指向最后一个元素，也就是最终的链表的头部。

代码实现

除了实现 reverse() 外，可以实现一个 LinkList 类封装起来，同时考虑链表的构造、析构、打印。最后可以写成模板，实现节点的 data 类型的范化。建议写题时多用这种思路，可以让代码更完善、更具工程性。

#include <iostream>

template <typename T>
class LinkList {
 public:
  LinkList() : head_(nullptr), tail_(nullptr) {}

  ~LinkList() {
    Node* list = head_;
    while (list) {
      Node* node = list;
      list = list->next;
      delete node;
    }

    head_ = nullptr;
    tail_ = nullptr;
  }

  // reverse without dummy node
  void reverse() {
    if (head_ == nullptr) return;

    Node *pre = nullptr, *cur = head_, *next = nullptr;
    while (cur) {
      next = cur->next;
      cur->next = pre;
      pre = cur;
      cur = next;
    }

    tail_ = head_;
    head_ = pre;
  }

  // print
  void print() const {
    if (head_ == nullptr) return;

    Node* list = head_;
    while (list) {
      std::cout << list->data << ' ';
      list = list->next;
    }
    std::cout << std::endl;
  }

  // insert
  void insert(T value) {
    Node* node = new Node(value);
    if (head_ == nullptr) {
      head_ = node;
      tail_ = node;
    } else {
      tail_->next = node;
      tail_ = node;
    }
  }

 private:
  struct Node {
    T data;
    Node* next;
    Node() = default;
    Node(T value) : data(value), next(nullptr) {}
  };

  Node* head_;
  Node* tail_;
};

int main() {
  int n = 10;
  LinkList<int> list;

  for (int i = 1; i <= n; ++i) {
    list.insert(i);
  }
  list.print();

  list.reverse();
  list.print();

  return 0;
}

2.2 使用 dummy node - 更通用

反转链表的时候，先创建一个 dummy node 指向原链表的头；
在反转的时候，逐个将节点插入到 dummy node 后面；
遍历到最后， dummy node 指向的就是新的链表的头；

#include <iostream>

template <typename T>
class LinkList {
 public:
  LinkList() : head_(nullptr), tail_(nullptr) {}

  ~LinkList() {
    Node* list = head_;
    while (list) {
      Node* node = list;
      list = list->next;
      delete node;
    }

    head_ = nullptr;
    tail_ = nullptr;
  }

  // reverse with dummy node
  void reverse() {
    if (head_ == nullptr) return;

    Node dummy_node;
    dummy_node.next = head_;

    Node *pre = &dummy_node, *cur = head_, *next = nullptr;
    while (cur->next) {
      next = cur->next;
      cur->next = next->next;
      next->next = pre->next;
      pre->next = next;
    }

    head_ = pre->next;
    tail_ = cur;
  }

  // print
  void print() const {
    if (head_ == nullptr) return;

    Node* list = head_;
    while (list) {
      std::cout << list->data << ' ';
      list = list->next;
    }
    std::cout << std::endl;
  }

  // insert
  void insert(T value) {
    Node* node = new Node(value);
    if (head_ == nullptr) {
      head_ = node;
      tail_ = node;
    } else {
      tail_->next = node;
      tail_ = node;
    }
  }

 private:
  struct Node {
    T data;
    Node* next;
    Node() = default;
    Node(T value) : data(value), next(nullptr) {}
  };

  Node* head_;
  Node* tail_;
};

int main() {
  int n = 10;
  LinkList<int> list;

  for (int i = 1; i <= n; ++i) {
    list.insert(i);
  }
  list.print();

  list.reverse();
  list.print();

  return 0;
}

3 总结

确实很基础，没什么好说的，这都没写出来，除了菜也没别的原因了。

目录CONTENT

反转链表 - 反转整个链表