反转链表

题面

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入： head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

输入： head = [1,2] 输出：[2,1]

示例 3：

输入： head = [] 输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

分析

• 要翻转链表，可以遍历链表，事先存储下个节点的指针，修改 next 为 pre 即可

• 代码实现

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode() : val(0), next(nullptr) {}
   *     ListNode(int x) : val(x), next(nullptr) {}
   *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   * };
   */
  class Solution {
  public:
      ListNode* reverseList(ListNode* head) {
          ListNode* cur = head;
          ListNode* pre = nullptr;
          while (cur != nullptr && cur->next != nullptr) {
              ListNode* next = cur->next;
              ListNode* next2 = nullptr;
              next2 = cur->next->next;
              cur->next->next = cur;
              cur->next = pre;
              pre = next;
              cur = next2;
          }
          if (cur != nullptr) {
              cur->next = pre;
          } else {
              cur = pre;
          }
          return cur;
      }
  };

• 简化逻辑，不需要关注下下个节点

  class Solution {
  public:
      ListNode* reverseList(ListNode* head) {
          ListNode* prev = nullptr;
          ListNode* curr = head;
          while (curr) {
              ListNode* next = curr->next;
              curr->next = prev;
              prev = curr;
              curr = next;
          }
          return prev;
      }
  };

• 递归实现：在递归中，一定是从链表的末尾开始反转的，因为递归会不断地进行深度遍历

  class Solution {
  public:
      ListNode* reverseList(ListNode* head) {
          ListNode* prev = nullptr;
          ListNode* curr = head;
          while (curr) {
              ListNode* next = curr->next;
              curr->next = prev;
              prev = curr;
              curr = next;
          }
          return prev;
      }
  };