共计 2401 个字符，预计需要花费 7 分钟才能阅读完成。
明天来看一道简略然而比拟常考的题，题的解法是很简略的，递归代码的话 硬背 都能记住，但真的把代码逻辑理清的人不是很多。我心愿你看完看完这篇文章之后能把递归和迭代的思路整个理分明，代码为什么会那么写，从而解脱背的窘境。
先看下题：
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
示例 1：
输出：head = [1,2,3,4,5]
输入：[5,4,3,2,1]
递归
咱们先来看看递归解法，递归首先是找递归终止条件，这里咱们假设是原函数就是递归调用函数，原函数是须要返回一个 ListNode, 所以比拟天然的想到当递归函数传的ListNode 为 null 或者下一个指针为 null 时退出以后层，代码如下：
if (head == null || head.next == null) {return head;}而后咱们定义一个节点 P 示意 head.next 的翻转后果。
ListNode p = reverseList(head.next);简略解释下，在没有执行 reverseList(head.next) 之前链表是 1->2->3->4->5; 当执行该函数之后，因为会进行递归调用，直到最初一个节点，所以节点 p 的指向为5->4->3->2->null; 这时候整个链表的指向为1->2<-3<-4<-5;
它离咱们最初的指标 null<-1<-2<-3<-4<-5 是不是很靠近了？咱们只须要将最初一步 2 指向 1，并且将 1 指向 Null 就能够。
留神这里不能用 p.next 指向 head，而应该用 head.next 指向 head。因为 p 指的是以 5 结尾的节点，它的 next 是 4，这样指的话会使 4 前面节点全副断掉。初学者很容易犯这种谬误，而后指着指着把本人搞晕。咱们这里间接应用 head.next 示意 2，而后把它下一个节点指向 1，再把 1 的下一个节点指向空。这里如果有点搞不清楚的，倡议翻一下我后面 k 个一组翻转链表那篇文章里写的做链表题的一些常识，你就会清晰很多。于是有了上面代码：
head.next.next = head;
head.next = null;那最初咱们应该返回的后果时什么呢？head.next 么？不是的，是 p。这时候 p 是从 5 开始指向 1 的残缺链表。
整合下递归的残缺代码如下：
if (head == null || head.next == null) {return head;}
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;当然，这么说你可能还是对 reverseList(head.next)这个函数的具体流程很纳闷，我一开始也是这样，这个可能须要你对递归有肯定熟练程度之后能力有概念。
你能够这么思考，当 head==null||head.next==null 时，就会跳出以后层，否则会始终往下走。
这里第一次跳进去是 head.next 值为 5 的时候，而后它会做什么呢？head.next.next=head这层栈调用的 head 参数是 4，因而会将 head.next 指向 head，就是 5 指向 4，而后将 4 指向 null。
这时候的链表形态是 1->2->3->4<-5 这样的。p 的形态是5->4->null。
而后会返回 p 到上一层栈函数，上一层的 head 是 3，head.next 是 4，执行 head.next.next = head;head.next = null 这两行代码之后整个链表形态是1->2->3<-4<-5。p 的形态是5->4->3->null。
而后在返回 p，反复上述过程，最初在以后函数失去 1->2<-3<-4<-5 这样的 p，通过最初两行代码反转之后失去整个反转之后的链表。
你依照我这个思路过两次，应该就大略晓得这个题的递归流程了。
这个画了一个示意图，你能够大略参考下，和下面思路对应，你能够对照着看：
迭代
接下来看看迭代的代码：
迭代的整个思路绝对递归简略很多，就是结构一个 prev 指针和一个 curr 指针，一开始 prev 指针为 null，curr 指针为 head，一直用 curr 指向 prev，做过这步后顺次将 prev 和 curr 后移，一直反复上述过程，直到 curr 为 null，而后这时候的 prev 就是翻转后的链表。
具体代码如下：
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
//1->2 变成 1 <-2，反转链表
curr.next = pre;
// 将 curr 和 next 像后移
pre = curr;
curr = next;
}
return pre;while 外面的代码大略说一下，因为 curr.next 在第二步会断掉，前面又会用到 curr.next，因而提前结构一个 next 指针指向 curr.next，这样在前面指针后移的时候不会出错。
具体过程你能够看上面这个示意图：
下面的代码其实还能够优化，curr 这个变量其实没什么用，咱们能够间接用 head 代表 curr。代码如下：
ListNode newHead = null;
while (head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;然而理论工程中不太倡议应用下面这种写法，因为它会扭转原始数据，如果传得这个参数是一个公共数据，有多个中央应用，你批改了这个数据会对其余模块也造成影响，所以比拟倡议用第一种写法。但如果你能必定没有其余中央会应用这个数据的话，第二种写法也是能够的。
写在最初
链表绝对于数组会难了解点，特地是老手，一开始链表指着指着就懵了，最初不晓得指到哪里去了。我一开始学也是这样，看链表题解法感觉就和看天书一样，但只有你长时间做题，重复回顾，把链表代码里一些套路 (也能够说是常识) 弄明确之后，再去了解就会清晰很多。
