單鏈表倒置

　我想你去很多家公司面試的時候，遇到單鏈表倒置的問題可能比較多，如果一定要給面試題來一個排名，估計也能上top10吧，其實這個

題目玩的是技巧和你對單鏈表的理解，其實我們仔細想想也不是很難，既然是倒置，那我們一定是一定要走一遍單鏈表的，對吧，那么走單鏈

表有兩種形式，遞歸和循環(huán)兩種方式，而遞歸正是壓棧和出棧，那么我們就想起來了，這不就是順序和逆序的關(guān)系嗎？第二種就是循環(huán)，還記

得我們曾今學(xué)習(xí)單鏈表的時候有一種插法叫做頭插法，這種插入復(fù)雜度為O(1),不好的地方就是順序插入的數(shù)字，出來的時候卻是反的，所以這

個不就是可以將原先的鏈表原地倒置過來嗎？

一：遞歸

　 說到遞歸，我們腦子里面一定要有一個V型圖，還有一個就是好記性不如爛筆頭，算法這東西很難用腦子想的清楚的，多畫畫圖就見青天了，

下面我就舉個簡單的例子：現(xiàn)有鏈表L={8,1,6,3}，需要將L倒置，然后我就畫好了V型圖。

從圖中可以看到，當我遞歸到3再出棧的時候，只需要將6賦給3.next，1賦給6.next，然后這樣以此類推。。。最后結(jié)果就出來了，貌似

口頭上描述起來很簡單，但是在寫代碼的時候需要注意以下幾個點，先上代碼說話。

 1         public LinkNode Reverse(LinkNode node) 2         { 3             if (node.next == null) 4                 return node; 5  6             var PRevNode = Reverse(node.next); 7  8             var temp = node.next; 9 10             temp.next = node;11 12             node.next = null;13 14             return prevNode;15         }

第一點：我們在走鏈表的時候，可以操控的只有兩個結(jié)點，node和node.next，所以遞歸出口的時候，一定不能使用最常見的寫法。

1       if (node == null)2            return node;

　　　 而應(yīng)該像下面這么寫，其實就告訴我們只需要走到6節(jié)點就行了，用6.next來判斷下是不是鏈尾，這樣做是方便我們進行node和

　　　node.next進行節(jié)點交換。

1             if (node.next == null)2                 return node;

第二點：當我們每一次出棧的時候，其實也是退到曾今壓棧時的方法環(huán)境中，進行節(jié)點交換的時候，也只能在當前的方法上下文中起效，比如

說：出棧到1的時候，其實3和6的節(jié)點已經(jīng)交換了，但是1這個方法環(huán)境不知道，它仍然指向6，但此時節(jié)點6.next再也不是3了，因為

　　　 曾今3和6進行了交換，所以這不是我們所期望的，所以在回退的時候，一定要有一個鏈表保存這個所有節(jié)點交換的集合，恰巧在鏈表中

有一個特征就是，只要我有一個指針始終指向頭結(jié)點的地址，它就相當于一個集合的功能了，因為我不管你后面節(jié)點怎么轉(zhuǎn)換，我都可以

通過head.next依次找到后面痙攣的所有結(jié)點，比如下圖中在出棧的過程中，每個出棧的方法環(huán)境中都依次交換了node和node.next結(jié)

點，而我的prevnode始終指向的是結(jié)點3，所以我通過3.next就可以找到后面所有的變化，所以這里就是prevnode的精妙之處。

最后看一下倒置的輸出結(jié)果：

二：非遞歸實現(xiàn)

　　如果你知道頭插法，那么循環(huán)實現(xiàn)真的很簡單，不像遞歸做法很難想到那個prevnode節(jié)點，我們知道頭插法是把新節(jié)點插入到鏈表的頭部，

而我們遍歷的時候又可以控制兩個節(jié)點node和node.next，所以依次采用頭插法，將node.next插入到node之前，有人說，那插入到node節(jié)

點之前不就亂了嗎？所以在操作之前，我可以把node.next先保存起來，比如放到申請的一個叫next的節(jié)點上，為了保存新轉(zhuǎn)換的節(jié)點，我們再

申請一個prev結(jié)點來保存頭插法中的新節(jié)點。

為了好理解，畫圖如下，其實這里要注意，結(jié)點還是那些結(jié)點，并沒有刪除再添加。

 1         public LinkNode Reserve(LinkNode node) 2         { 3             LinkNode prev = null; 4             LinkNode next = null; 5  6             while (node != null) 7             { 8                 next = node.next; 9 10                 node.next = prev;11 12                 prev = node;13 14                 node = next;15             }16             return prev;17         }

其實我們發(fā)現(xiàn)，代碼只有那么一點點，但是信息量還是蠻大的，這些東西要是用口頭描述還是很累的。