题目描述

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

解法一：迭代

迭代法应该是我们最容易想到的常规方法，也比较符合人的思维逻辑。其核心思想就是通过两个指针移动，来 一个一个的修改链表的指向方向。

 1class Solution {
 2public:
 3    ListNode* reverseList(ListNode* head) {
 4        if (!head || !head->next) return head;
 5        ListNode* prev = nullptr;
 6        ListNode* cur = head;
 7        while (cur) {
 8            ListNode* tmp = cur->next;
 9            cur->next = prev;
10            prev = cur;
11            cur = tmp;
12        }
13        return prev;
14    }
15};

解法二：递归

第二个方法就是使用递归，递归这种方法虽然不太容易能够想到，但是代码却很简洁。

 1class Solution {
 2public:
 3    ListNode* reverseList(ListNode* head) {
 4        if (!head || !head->next) return head;
 5        ListNode* newHead = reverseList(head->next);
 6        head->next->next = head;
 7        head->next = nullptr;
 8        return newHead;
 9    }
10};