明天来看一道简略然而比拟常考的题，题的解法是很简略的，递归代码的话硬背都能记住，但真的把代码逻辑理清的人不是很多。我心愿你看完看完这篇文章之后能把递归和迭代的思路整个理分明，代码为什么会那么写，从而解脱背的窘境。
先看下题：
给你单链表的头节点 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;然而理论工程中不太倡议应用下面这种写法，因为它会扭转原始数据，如果传得这个参数是一个公共数据，有多个中央应用，你批改了这个数据会对其余模块也造成影响，所以比拟倡议用第一种写法。但如果你能必定没有其余中央会应用这个数据的话，第二种写法也是能够的。
写在最初
链表绝对于数组会难了解点，特地是老手，一开始链表指着指着就懵了，最初不晓得指到哪里去了。我一开始学也是这样，看链表题解法感觉就和看天书一样，但只有你长时间做题，重复回顾，把链表代码里一些套路(也能够说是常识)弄明确之后，再去了解就会清晰很多。
