Leetcode 206.反转链表

题目描述：

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

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

示例 1：

1
2

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

示例 2：

1
2

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

示例 3：

1
2

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

提示：

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

链接：

https://leetcode-cn.com/problems/reverse-linked-list

题目分析

1.迭代

  按照链表顺序逐个结点反向连接即可。注意反向连接之前需要先保存好下个结点，获取 next 的前提是指针不为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode *pre = head;
        ListNode *p = head->next;
        head->next = nullptr;
        while(p != nullptr){
            ListNode *next = p->next;
            p->next = pre;
            pre = p;
            p = next;
        }
        return pre;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是链表的长度。我们对链表进行了一次遍历。
  空间复杂度：$O(1)$。我们只需要常数个指针的空间。

2.递归

  递归解法应该也是遍历链表，那么我们需要思考子递归的结果能够给我们带来什么。函数的结果是反转链表，如果我们将下一个结点作为头结点进行递归，那么我们应该得到的是一条除去头结点的反转链表。就像下面这样，1->2->3->4->...->n 变成 1->2<-3<-4<-...<-n。那么我们只需要将下一个结点的 next 赋为头结点，将头结点的 next 置为空，得到的就是结果。
  需要注意的是函数的返回结果是反转后链表的头结点，而我们拼接上当前结点后的返回结果也是这个结点。递归的终止条件就是只有一个结点的时候，反转链表的结果其实是相同的，并且这个结点实际上就是新链表的头结点，直接进行返回。

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode *result = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是链表的长度。递归实际上也是对链表进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 是链表的长度。递归的深度就是链表的长度。