今天來看一道簡單但是比較衬匀冢考的題运吓，題的解法是很簡單的间景，遞歸代碼的話硬背都能記住，但真的把代碼邏輯理清的人不是很多菲嘴。我希望你看完看完這篇文章之后能把遞歸和迭代的思路整個理清楚，代碼為什么會那么寫，從而擺脫背的困境龄坪。
先看下題：
給你單鏈表的頭節(jié)點 head 昭雌，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表健田。
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
遞歸
我們先來看看遞歸解法烛卧，遞歸首先是找遞歸終止條件，這里我們假定是原函數(shù)就是遞歸調(diào)用函數(shù)妓局，原函數(shù)是需要返回一個ListNode,所以比較自然的想到當遞歸函數(shù)傳的ListNode為null或者下一個指針為null時退出當前層唱星，代碼如下：
if (head == null || head.next == null) {
return head;
}
然后我們定義一個節(jié)點P表示head.next的翻轉(zhuǎn)結(jié)果。
ListNode p = reverseList(head.next);
簡單解釋下跟磨，在沒有執(zhí)行reverseList(head.next)之前鏈表是1->2->3->4->5;當執(zhí)行該函數(shù)之后间聊，由于會進行遞歸調(diào)用，直到最后一個節(jié)點抵拘，所以節(jié)點p的指向為5->4->3->2->null;這時候整個鏈表的指向為1->2<-3<-4<-5;
它離我們最后的目標null<-1<-2<-3<-4<-5是不是很接近了哎榴？我們只需要將最后一步2指向1，并且將1指向Null就可以僵蛛。
注意這里不能用p.next指向head尚蝌，而應(yīng)該用head.next指向head。因為p指的是以5開頭的節(jié)點充尉，它的next是4飘言，這樣指的話會使4后面節(jié)點全部斷掉。初學者很容易犯這種錯誤驼侠，然后指著指著把自己搞暈姿鸿。我們這里直接使用head.next表示2，然后把它下一個節(jié)點指向1倒源，再把1的下一個節(jié)點指向空苛预。這里如果有點搞不清楚的，建議翻一下我前面k個一組翻轉(zhuǎn)鏈表那篇文章里寫的做鏈表題的一些常識笋熬，你就會清晰很多热某。于是有了下面代碼：
head.next.next = head;
head.next = null;
那最后我們應(yīng)該返回的結(jié)果時什么呢？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)這個函數(shù)的具體流程很疑惑，我一開始也是這樣蔬捷，這個可能需要你對遞歸有一定熟練程度之后才能有概念垄提。
你可以這么思考，當head==null||head.next==null時周拐，就會跳出當前層，否則會一直往下走审丘。
這里第一次跳出來是head.next值為5的時候滩报，然后它會做什么呢播急？head.next.next=head這層棧調(diào)用的head參數(shù)是4，因此會將head.next指向head可训，就是5指向4握截，然后將4指向null烂叔。
這時候的鏈表形狀是1->2->3->4<-5這樣的蒜鸡。p的形狀是5->4->null。
然后會返回p到上一層棧函數(shù)康聂，上一層的head是3胞四，head.next是4，執(zhí)行head.next.next = head;head.next = null這兩行代碼之后整個鏈表形狀是1->2->3<-4<-5氓侧。p的形狀是5->4->3->null导狡。
然后在返回p，重復(fù)上述過程独郎，最后在當前函數(shù)得到1->2<-3<-4<-5這樣的p，經(jīng)過最后兩行代碼反轉(zhuǎn)之后得到整個反轉(zhuǎn)之后的鏈表氓癌。
你按照我這個思路過兩次，應(yīng)該就大概知道這個題的遞歸流程了反粥。
這個畫了一個示意圖疲迂，你可以大概參考下尤蒿，和上面思路對應(yīng)，你可以對照著看：
迭代
接下來看看迭代的代碼：
迭代的整個思路相對遞歸簡單很多，就是構(gòu)造一個prev指針和一個curr指針演怎，一開始prev指針為null避乏，curr指針為head拍皮，不斷用curr指向prev，做過這步后依次將prev和curr后移咆耿，不斷重復(fù)上述過程爹橱，直到curr為null愧驱，然后這時候的prev就是翻轉(zhuǎn)后的鏈表慰技。
具體代碼如下：
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
//1->2變成1<-2，反轉(zhuǎn)鏈表
curr.next = pre;
//將curr和next像后移
pre = curr;
curr = next;
}
return pre;
while里面的代碼大概說一下组砚，因為curr.next在第二步會斷掉，后面又會用到curr.next糟红，因此提前構(gòu)造一個next指針指向curr.next艾帐，這樣在后面指針后移的時候不會出錯。
具體過程你可以看下面這個示意圖：
上面的代碼其實還可以優(yōu)化柒爸，curr這個變量其實沒什么用准浴，我們可以直接用head代表curr。代碼如下：
ListNode newHead = null;
while (head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
但是實際工程中不太建議使用上面這種寫法兄裂，因為它會改變原始數(shù)據(jù)句旱，如果傳得這個參數(shù)是一個公共數(shù)據(jù)阳藻，有多個地方使用，你修改了這個數(shù)據(jù)會對其他模塊也造成影響谈撒，所以比較建議用第一種寫法。但如果你能肯定沒有其他地方會使用這個數(shù)據(jù)的話啃匿，第二種寫法也是可以的蛔外。
寫在最后
鏈表相對于數(shù)組會難理解點夹厌，特別是新手裆悄，一開始鏈表指著指著就懵了或南，最后不知道指到哪里去了。我一開始學也是這樣艾君，看鏈表題解法感覺就和看天書一樣蹬癌，但只要你長時間做題，反復(fù)回顧虹茶，把鏈表代碼里一些套路(也可以說是常識)弄明白之后冀瓦，再去理解就會清晰很多。
