劍指 Offer 24. 反轉連結清單

題目

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

示例:

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

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

限制：

0 <= 節點個數 <= 5000

其中，連結清單的結構為：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
           

思路

1、用頭插法實作連結清單的反轉

剛開始看到這道題的思路，就是最簡單、最暴力的解法----再定義一個頭節點，用頭插法實作連結清單的反轉。但是，在實作的過程中，花費了不小功夫來調bug。主要的原因，還是讀題目不夠清晰！

題目說的是：輸入一個連結清單的頭節點，要求實作連結清單的反轉。

但是，需要注意的是，給的示例為：

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

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

給出的示例表明，其實這個 輸入的“連結清單的頭節點”，并不是真正的頭節點 => 實際上，輸入的連結清單，是沒有頭節點的，是以輸入的head，是該連結清單中，第一個節點不假，但是該節點的val屬性，即：在連結清單不空的情況下，head.val 存儲的是有資料的！！！！！！

是以，代碼實作為：

class Solution {
    public ListNode reverseList(ListNode head) {
        /*
        實際上進行的操作：将head對應的單連結清單，進行周遊，并将周遊到的節點按照頭插法，插入到新的頭節點reverseHead對應的單連結清單中
        注意：輸入的單連結清單實際上是不帶頭節點的，head就是實際存儲資料的第一個節點
        */
        if(head == null){
            //一個節點都沒有的情況下，直接傳回原來的頭節點即可
            return head;
        }

        //定義新的"頭節點reverseHead,
        ListNode reverseHead = new ListNode(head.val);
        //定義一個輔助節點，用于幫助在head對應的連結清單中進行周遊
        //cur實際上對應的是head對應的單連結清單中，head節點後的第一個節點
        ListNode cur = head.next;
        ListNode next = null;//用于：幫助實作head所在連結清單中的cur的後移

        //循環周遊的過程
        while(cur != null ){//當head對應的連結清單中，除了head節點之外還有其他節點時
            //暫存目前節點cur的下一個節點
            next = cur.next;
            //實作在reverseHead的連結清單中的頭插法"reverseHead是真正的帶頭節點"
            cur.next = reverseHead;
            reverseHead = cur;
            //在head的連結清單中，要進行實作周遊的必要操作------後移
            cur = next;//這裡一定要有next這個變量的存在，不然在進行過reverseHead中的頭插操作後，會找不到head中原來的cur後面的那個節點
        }
        return reverseHead;
    }
}
           

2、手動實作相鄰節點直接連結的反向（也叫雙指針法）

----時間複雜度、空間複雜度，均要比 1 的直接頭插法實作的方式好一些

• 使用雙指針(實際上是有三個指針，一個用來周遊，其餘兩個都是作為輔助指針)來解題：

• 定義三個指針：pre、cur、next，其中cur用來周遊，而pre.next==cur，next=cur.next；

1. 将原來的單連結清單的整個方向進行轉換，即：
   • 将pre.next=cur改為：pre=cur.next；
   • 然後，将三個指針整體往正在進行的周遊的方向移動一個機關：
   • ---->pre=cur，cur=next，next=next.next
2. 簡言之，pre指針是用來輔助 實作連結清單方向轉換的一個變量；
   • =>而next指針是用來輔助周遊的一個變量（因為一個節點的next域隻能存儲一個其他節點，是以，如果cur建立起一個新的next域指向的pre的鍊連接配接，就需要一個next指針來儲存該cur節點原來的next域指向的節點）；
   • =>而cur指針，就是用來進行周遊的指針，它既可以用來建立逆向的連結清單連接配接，又可以作為三個指針向前周遊的一個參考基準
   • 而控制循環進行的條件為：cur！=null，即：pre要作為最終傳回的“頭節點”

是以，代碼實作為：

class Solution {
    public ListNode reverseList(ListNode head) {
        //連結清單一個節點都沒有或者隻有一個節點，沒有反轉的必要
        if( head==null || head.next==null){
            return head;
        }
        //此時連結清單至少有兩個節點
        ListNode cur = head.next;
        ListNode pre = head;
        ListNode next = null ;
        //head節點最終在實作反轉之後是連結清單的末尾
        head.next = null;
        while(cur != null){//當cur是最後一個節點時，循環終止
            //在建立新的連結之前，先保留下來原來的連結
            next = cur.next;
            //建立反向的連結
            cur.next = pre;
            //跟新剩餘的2個指針
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
           

3、 使用遞歸的方法實作反轉

----是一個提升吧，強大又難搞的遞歸：

*
           

1. 可以這樣對問題進行分析：把大問題劃分成小問題：

   • 1）假設連結清單的其餘部分已經實作反轉，那麼如何實作前面的部分的反轉？

     ----cur.next.next = cur;

   • 2）遞歸的結束條件是什麼？

     ----cur.next == null;

   • 3）實作遞歸的方法中，如何确定1）、2）兩步驟的順序？

     實際上是跟樹的周遊的順序是一樣的，應該在遞歸結束之後，回溯的過程中，實作連結方向的改變，不然的話，會由于連結方向的改變，導緻還沒有周遊到的節點丢失（因為沒有節點連結向該節點而丢失）

   • 4）需要注意的是，要将最初的head節點的next域的值，設定為null。不然會出現 環。

     Attention:回溯時，每到一個節點，就将該節點當做新連結清單的尾節點來進行處理

   • 5）以上幾步的順序為：2）=> 1） => 4）
2. 其實，當該連結清單 不包含節點 或者 隻包含一個節點的情況下，可以不用調用遞歸，在剛開始，直接return head。
   • ------可以和遞歸的終止條件 合并

是以，代碼實作為：

class Solution {
    public ListNode reverseList(ListNode head) {
       
        if(head == null || head.next == null){
            //1、沒有節點或者隻包含一個節點，不用反轉
            //2、也作為遞歸的終止條件
            return head;
        }
		//目前節點不是遞歸終點時，進行的操作
        ListNode newHead = reverseList(head.next);//遞歸調用
        head.next.next = head;
        head.next = null;
        return newHead;
       
    }
}
           

總結一下資料結構中連結清單問題 解決時候的真理：

涉及到連結清單的操作，一定要在紙上把過程先畫出來，再寫程式。