共计 2308 个字符，预计需要花费 6 分钟才能阅读完成。
反转链表 这题真的是面试十分喜爱考的了，这题看起来简略，然而能用 两种办法 一遍 bug free 也是不容易的，面试的时候能够筛下来一大批人，无论是对 junior 还是 senior 面试都很爱考。
明天齐姐就带你梳理分明思路，思路清楚了能力 写码如有神。
题目
这是从力扣中文站上截下来的，然而这个输入不太形象。
对链表的反转，并不是要把它理论翻个个，只是动一动 next 指针就好了。
什么意思呢？
咱们先看对数组进行反转。
数组是一个物理上间断存储的数据结构，反转之后原来放 1 的地位就变成了放 5.
然而链表并不是，因为链表在物理上是不间断的，它的每个单元 ListNode 是通过 next 指针连贯在一起的，而每个 ListNode 之间在内存里并不一定是挨着的。
所以反转链表，就不是非要把 1 的地位放 5，因为它们想在哪在哪。
那么怎么保障这个程序呢？
- 就是 next 指针。
沿着 next 指针的方向走上来，就是链表的程序。这也就保障了，只有咱们拿到了头节点，就掌控了整个 LinkedList.
那么题目中的例子，形象点是这个样子滴：
也就是元素本人不必动，只须要动动小指针，就是反转了。
递归解法
递归的三步骤大家还记得吗？
Base case + 拆解 + 组合
不记得的连忙在公众号内回复「递归」二字，获取递归的入门篇详解。
那么咱们来看这个题的：
base case:
当只有一个 node，或者没有 node 了呗，也就是
if(node == null || node.next == null) {return node;}其实呢，只剩一个 node 的时候严格来讲并不是 base case，而是 corner case，
因为它本能够再 break down 到 node == null 的，但因为前面有对 node.next 的 dereference 操作，所以不能省略。
拆解：
递归的拆解就是把大问题，分解成小一点点的问题，直到 base case 能够返回，进行第三步的组合。
那么这里就是
组合：
组合的意思是，假如咱们可能拿到小问题的解，那么用小问题的解去结构大问题的解。
那么这个问题里如何结构呢？
这里很显著，在 2 前面接上 1 就行了，然而 怎么拿到 2 呢？
别忘了，原问题里，此时还有 1 指向 2 呢～
也就是 node1.next = node2，
而后把 2 指向 1：node2.next = node1
合起来就是：node1.next.next = node1
思路清楚就不绕，看着感觉绕的就是没想分明哼～
代码
递归的代码写起来都很简洁：
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) {return head;}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}工夫复杂度
咱们在「递归」这篇文章里说过，递归的工夫复杂度分析方法就是把 递归树画进去，每个节点的工夫加起来 就行了。
这个递归树是一个很简略的单项链表，每个节点上做的就是那三行代码，也就是「组合」做的事，即 O(1) 的工夫，总共有 n 个节点，那么总的工夫就是 O(n).
空间复杂度
那看递归树也很显著了，每一层也就用了点小变量，是 O(1)，所以总的空间共是 O(n).
Iterative 解法
（谁能通知我这个中文的业余说法。。
Iterative 的思路就是：
过一遍这个 Linked List，边过边把这个 node 的 next 指针指向后面那个 node，直到过齐全部。
这样说太形象，面试时也是，间接过例子。
那也就是把 1 的 next 指针翻过来指向 NULL；
把 2 的 next 指针翻过来指向 1；
把 3 的 next 指针翻过来指向 2；
…
所以咱们还须要一个变量来记录以后 node 的前一个 node，无妨设为 prev.
同时呢，一旦咱们把指针翻转过来，前面的那个 node 就丢了有木有！所以还须要有个额定的变量当时记录下前面的 node，设为 nxt，这样才不至于走丢～
Step1.
翻转箭头：把 1 的 next 指针指向 NULL；
这样子，同时咱们也明确了，prev 的初始化应该是 NULL.
而后把这仨变量都挪动到下一个地位：
Step2.
翻转箭头：把 2 的 next 指针指向 1，
而后三人行：
Step3.
翻转箭头：把 3 的 next 指针指向 2，
再齐步走：
Step4.
再把 4 的反过来：
再往后走：
Step5.
再把 5 的 next 反过来：
然而因为咱们的 while 循环蕴含了
「翻转箭头」+「三人行」
两个步骤，所以还须要走完最初一个三人行，变成：
很多同学搞不清楚这个 while 循环的完结条件，其实很简略，你就 走个例子画画图 嘛！
那完结条件就是 curr = null 的时候，
最初返回的是 prev.
好了，看代码吧：
class Solution {public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null) {
ListNode nxt = curr.next;
curr.next = prev; // 翻转箭头
prev = curr; // 三人行
curr = nxt; // 三人行
}
return prev;
}
}工夫复杂度
这里的工夫复杂度很显著了，就是过了一遍这个链表，所以是 O(n).
空间复杂度
空间是 O(1).
如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！
我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！
更多干货文章见我的 Github: https://github.com/xiaoqi6666…
