206-Reverse Linked list

文章目录

题目思路方法1：迭代方法2：递归

题目

Reverse 反转 a singly linked list 单向链表.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively 迭代 or recursively 递归. Could you implement both 应用这两种方法?

思路

方法1：迭代

假设存在链表 1 → 2 → 3 → Ø

要把它改成 Ø ← 1 ← 2 ← 3

这样子对齐后，就能够明白对传入的每一个元素的操作

在遍历列表时，将当前节点的 next 指针改为指向前一个元素（第一个元素1的时候就指向None）。

由于节点没有引用其上一个节点，因此必须事先用一个临时变量存储其前一个元素。

在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

复杂度分析

时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)空间复杂度：O(1)

方法2：递归