Given the head of a singly linked list, reverse the list, and return the reversed list.

Q：单链表反转

Constraints:

  • The number of nodes in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Example 1:
image.png
**Input:** head = [1,2,3,4,5]
**Output:** [5,4,3,2,1]

Example 2:
image.png
**Input:** head = [1,2]
**Output:** [2,1]

Example 3:
**Input:** head = []
**Output:** []

方法1：循环+头插

  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.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseList(ListNode* head) {
  14.         // 循环+头插
  15.         if(head == nullptr || head->next == nullptr){
  16.             return head;
  17.         }
  19.         // 使用带额外头结点的新链表
  20.         ListNode* newHead = new ListNode();
  21.         ListNode* p = head;
  22.         ListNode* q = nullptr;
  23.         while(p != nullptr){
  24.             // 遍历旧链表，将旧链表的结点一个个以头插的方式加入到新链表中
  25.             q = p->next;
  27.             p->next = newHead->next;
  28.             newHead->next = p;
  30.             p = q;
  31.         }
  33.         p = newHead->next;
  35.         delete newHead;
  36.         newHead = nullptr;
  38.         return p;
  39.     }
  40. };

运行效率评价

Success Details
Runtime: 8 ms, faster than 63.09% of C++ online submissions for Reverse Linked List.
Memory Usage: 8.4 MB, less than 41.66% of C++ online submissions for Reverse Linked List.

方法2：递归法

递归方法写起来很容易，也很优美。
从链表末端往前修改。

实现代码：

  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.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseList(ListNode* head) {
  14.         // 递归法
  15.         if(head == nullptr || head->next == nullptr){
  16.             return head;
  17.         }
  19.         ListNode* last = reverseList(head->next);
  20.         head->next->next = head;
  21.         head->next = nullptr;
  22.         return last;
  23.     }
  24. };

代码图解：

yuque_diagram.jpg

运行效率

Success Details
Runtime: 8 ms, faster than 63.09% of C++ online submissions for Reverse Linked List.
Memory Usage: 8.4 MB, less than 20.51% of C++ online submissions for Reverse Linked List.