劍指offer 面試題24：反轉連結清單

題目：

定義一個函數，輸入一個連結清單的頭節點，反轉該連結清單并輸出反轉後連結清單的頭節點。

示例:

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

限制：

0 <= 節點個數 <= 5000

一、疊代

1. 選值，next之後插到前面。

public class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val=x;//構造方法
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode ans=new ListNode(head.val);
        head=head.next;
        while(head!=null){
            ListNode node=new ListNode(head.val);
            node.next=ans;
            ans=node;
            head=head.next;
        }
        return ans;
    }
}
           

1. 改箭頭，将每個箭頭逆序

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

相當于

輸入:       1->2->3->4->5->NULL
輸出: NULL<-1<-2<-3<-4<-5
           

意思也就是說，我們除了一個一個值都取出來之外，還可以直接在連結清單上進行箭頭方向的修改，将它們指向反方向。

我們需要三個節點，一個pre，一個cur，一個nex，分别代表前一個，現在的，和後一個。

• cur指向 pre 之後，pre 換成 cur，那麼在 cur 取了 next 之後就會跑到前面，是以需要在改變方向之前先把 nex 取到正确位置；

nex=cur.next;
            cur.next=pre;
           

• 在這一次方向翻轉之後要更新位置，pre要改到目前的 cur；

• 然後cur要更新到 nex ,(使用nex 節點是必要的，如果采用 cur 直接指向下一個，此時箭頭已經反了，就會取到前面)；

完整代碼如下：

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode pre=null;
        ListNode cur=head;
        ListNode nex=null;
        while(cur!=null){
            nex=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nex;//最終跳出cur會為空，是以結果return pre
        }
        return pre;
    }
}
           

二、遞歸

類似與上面翻轉箭頭方向的方法。

遞歸的向下翻轉箭頭，直到找到最後一個節點，然後開始翻轉，但是要保證 return 回來的是最後一個節點。

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        
        ListNode cur=reverseList(head.next);

        head.next.next=head;
        head.next=null;
        return cur;
    }
}
           

再來看這個代碼：

if(head==null||head.next==null){
            return head;
}
           

這個判斷的第一個條件是判斷初始的連結清單是否為空，第二個條件才是真正遞歸的判斷條件。

緊接上一步直接就遞歸調用了，可以看出這個遞歸的目的僅僅是找到 倒數第二個節點，而已。

因為比如 1->2->3->4->5->NULL，遞歸進行到 4.next 傳入括号内，也就是 5 作為下一輪的 head，發現 5.next 為空，傳回了 5，那麼 cur 就是 5.

head.next.next=head;
        head.next=null;
        return cur;
           

當從上一步傳回後，進行了目前的 head 的操作，此時的 head 是 4 ，然後讓 5 指向了 4 ，完成了最後一個箭頭的逆向；

然後将倒數第二個節點的 next 置空，防止環路産生；

然後 return cur，也就是把最後一個節點帶回去了。

注意，這一輪開始往前的每一輪，遞歸的傳回值都變成了 cur =5 ，也就是最後一個節點，因為上層的 if 條件都不滿足，那麼在最底層傳回一個節點之後，上層的每一層都進行一個箭頭的逆序（箭頭逆序操作裡面和 cur 無關），然後把 cur 傳回。

最後就達到了，逆序所有箭頭，然後傳回了最後一個節點的效果。