思路1：用栈的方式，用栈存入每个节点
思路2：递归
思路3：双指针,迭代， 既然可以用递归，则也可以用正向迭代的方式。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */

栈

  1. ListNode* reverseList(ListNode* head) {
  2.     if (!head) return NULL;
  3.     std::stack<ListNode*> s;
  4.     while(head) {
  5.         s.push(head);
  6.         head = head->next;
  7.     }
  8.     ListNode* node = s.top(); s.pop();
  9.     ListNode* dummy_node = node;
  10.     while(!s.empty()) {
  11.         node->next = s.top(); s.pop();
  12.         node = node->next;
  13.     }
  14.     node->next = NULL;
  15.     return dummy_node;
  16. }

递归

  1. ListNode* reverseList(ListNode* head) {
  2.     if (head == nullptr || head->next == nullptr)
  3.         return head;
  4.     ListNode* tmp = reverseList(head->next);
  5.     head->next->next = head;
  6.     head->next = nullptr;
  7.     return tmp;
  8. }

双指针迭代

  1.  ListNode* reverseList(ListNode* head) {
  2.         if (head == nullptr || head->next == nullptr)
  3.             return head;
  5.         ListNode* pre = nullptr;
  6.         ListNode* cur = head;
  7.         while(cur) {
  8.             ListNode* next_node = cur->next; // 这里要注意先存下一个结点。否则next指向前一个结点时，下一个结点就丢失了。
  9.             cur->next = pre;          // 改变指向
  10.             pre = cur;                // pre 指针和 cur 指针迭代
  11.             cur = next_node;
  12.         }
  13.         return pre;
  14.     }

画个图，其实就很容易理解
image.png