說兩句

單鏈表是一種基本的數(shù)據(jù)結(jié)構(gòu),也是現(xiàn)在技術(shù)面試經(jīng)?？嫉綎|西(我曾在這跌倒過,那叫個慘,誰讓我們平時并不注重這些基本算法呢),所以呢,身為技術(shù)人員,還是要多看看這些數(shù)據(jù)算法,萬一哪天我們都成為大神呢,哈哈哈!

單鏈表反轉(zhuǎn)

1. 遞歸思想

遞歸思想,
重點問題一:在于找出遞歸退出點,顯然單鏈表反轉(zhuǎn)退出點在于尾節(jié)點的nex節(jié)點為null的判斷上
重點問題二:遞歸過程中處理邏輯.遞歸思想每次處理的都是關(guān)聯(lián)的兩個元素,其實反轉(zhuǎn)的重點思想在于將原有下級元素的next設(shè)置為它的父節(jié)點,而它的父節(jié)點會在遞歸的下次后將處理它的下一個節(jié)點的反轉(zhuǎn)邏輯.
總結(jié)如下圖,每次遞歸返回當(dāng)前節(jié)點保存了它下一個節(jié)點的引用,然后反轉(zhuǎn)本節(jié)點和下一個節(jié)點,本節(jié)點置為尾節(jié)點,以此類推:

遞歸反轉(zhuǎn)單鏈表.png

核心代碼如下:

public  static Node reverser(Node root){
//1.跳出條件
  if(root ==null||root.getNext()==null){
      return node;    
  }
 //2. 遞歸調(diào)用,直到最后節(jié)點
Node   next=reverser(root.getNext());
//3. 遞歸每步進行逐步反轉(zhuǎn)
root.getNext().setNext(root);
root.setNext(null);
//4. 返回新的尾節(jié)點
return next;
}

// 2. 三指針循環(huán)法
關(guān)鍵點:

1. 解決循環(huán)反轉(zhuǎn)過程中斷鏈問題
2. 三個指針后移,避免死循環(huán)問題

總結(jié)如下圖,利用三個起始位置不同的指針,兩個臨時變量逐步后移,當(dāng)出現(xiàn)斷鏈時,通過第三個指針不斷續(xù)接.

三指針反轉(zhuǎn).png

代碼:

    /**
     * 循環(huán)進行反轉(zhuǎn)
     */
    public static Node reverser1(Node node) {

        //空鏈表或只有一個節(jié)點，直接返回
        if (node == null || node.getNext() == null) {
            return node;
        }
        //三個指針，一個temp先走了兩步，后續(xù)每次一步


        //指針一，當(dāng)前待反轉(zhuǎn)節(jié)點，起步點為1
        Node root=node;

        //指針二，每次緩存當(dāng)前節(jié)點的下一個節(jié)點，起步點為2
        Node preNode=node.getNext();


        //指針三，為待反轉(zhuǎn)節(jié)點待下一個節(jié)點，用來解決反轉(zhuǎn)后斷鏈問題，起步點為3
        Node temp = node.getNext().getNext();

        //當(dāng)前節(jié)點待下一個節(jié)點，用來緩存待反轉(zhuǎn)的節(jié)點
        if (temp == null) {
            //鏈表長度為2，直接反轉(zhuǎn)
            node.getNext().setNext(node);
            root=node.getNext();
            node.setNext(null);
        } else {
            //鏈表長度大于2時
            //跳出條件為快指針為null時，此時已經(jīng)循環(huán)到鏈表最后兩位
            while (temp!=null) {

                //通過指針二實現(xiàn)反轉(zhuǎn)
                preNode.setNext(root);

                //當(dāng)前節(jié)點后移一步
                root=preNode;

                //指針二后移一步
                preNode=temp;

                //指針三后移一步
                temp=temp.getNext();
            }

            //最后兩位處理，將最后兩個節(jié)點進行反轉(zhuǎn)
            preNode.setNext(root);
            root=preNode;
            //把原鏈表首節(jié)點的下一個節(jié)點置為空
            node.setNext(null);
        }


        return root;

    }

可以看出兩個方法,遞歸法會出現(xiàn)兩個節(jié)點指向同一節(jié)點情況,三指針法會出現(xiàn)斷鏈情況.比較而言,遞歸法更簡潔.