如何反转链表？

如何反转链表？

Head -> a -> b ->c -> null 反转为 c -> b -> a -> head -> null

单向链表反转(C++) #

Node 结构体

struct Node {
  int value;
  Node *next;
  Node() : value(0), next(nullptr) {}
  Node(int x) : value(x), next(nullptr) {}
  Node(int x, Node *next) : value(x), next(next) {}
};

反转操作

Node *reverseLinkedList(Node *head) {
  Node *pre = nullptr, *next = nullptr;
  while (head != nullptr) {
    next = head->next;
    head->next = pre;
    pre = head;
    head = next;
  }
  return pre;
}

双向链表反转(C++) #

struct DoubleNode {
  int value;
  DoubleNode *next;
  DoubleNode *pre;
  DoubleNode() : value(0), next(nullptr), pre(nullptr) {}
  DoubleNode(int x) : value(x), next(nullptr), pre(nullptr) {}
  DoubleNode(int x, DoubleNode *next, DoubleNode *pre)
      : value(x), next(next), pre(pre) {}
};

DoubleNode *reverseDoubleLinkedList(DoubleNode *head) {
  DoubleNode *pre = nullptr, *next = nullptr;
  while (head != nullptr) {
    next = head->next;
    head->next = pre;
    head->pre = next; // 比单向链表反转多了一步操作！
    pre = head;
    head = next;
  }
  return pre;
}