數(shù)據(jù)結(jié)構(gòu)與算法

1. 單鏈表的結(jié)點(diǎn)結(jié)構(gòu)

• data域：存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；
• next域：存儲(chǔ)直接后繼位置的域稱為指針域，它是存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）。
• data域+ next域：組成數(shù)據(jù)ai的存儲(chǔ)映射，稱為結(jié)點(diǎn)；

注意

• ①鏈表通過每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。
• ②每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表（Single Linked List）。

創(chuàng)建一結(jié)點(diǎn)類，其Java代碼如下：

class Node {
    private int Data;// 數(shù)據(jù)域
    private Node Next;// 指針域
    public Node(int Data) {
        // super();
        this.Data = Data;
    }
    public int getData() {
        return Data;
    }
    public void setData(int Data) {
        this.Data = Data;
    }

    public Node getNext() {
        return Next;
    }
    public void setNext(Node Next) {
        this.Next = Next;
    }
}

2 反轉(zhuǎn)的方法--遞歸反轉(zhuǎn)法

• 在反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之前先反轉(zhuǎn)后續(xù)節(jié)點(diǎn)。這樣從頭結(jié)點(diǎn)開始，層層深入直到尾結(jié)點(diǎn)才開始反轉(zhuǎn)指針域的指向。
• 從尾結(jié)點(diǎn)開始，逆向反轉(zhuǎn)各個(gè)結(jié)點(diǎn)的指針域指向

    /**
     * 遞歸，在反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之前先反轉(zhuǎn)后續(xù)節(jié)點(diǎn)
     */
    public static Node recursiveReverse(Node currentNode) {
        if (currentNode == null || currentNode.getNext() == null) {
            return currentNode;
        }

        Node returnNode = recursiveReverse(currentNode.getNext());
        //這里是重點(diǎn)。
        //當(dāng)前節(jié)點(diǎn)（currentNode）的下一個(gè)節(jié)點(diǎn)，正好是返回節(jié)點(diǎn)returnNode的最后一個(gè)節(jié)點(diǎn)
        currentNode.getNext().setNext(currentNode);
        currentNode.setNext(null);
        return returnNode;
    }

分析上述過程

• 1. 原始鏈表是1-2-3-4-5-6
• 2. 第一次調(diào)用即recursiveReverse(1)！=null && recursiveReverse(1).getNext()！=null 直到--最后一次。

• 第一次返回6
  即返回后 returnNode=6；currentNode=5-6；
  

  TIM截圖20180906110411.png
  
  然后設(shè)置currentNode.getNext().setNext(currentNode);
  那么現(xiàn)在的returnNode=6-5-6...；currentNode=5-6-5-6...
  
  TIM截圖20180906111139.png
  
  接著currentNode.setNext(null);
  
  TIM截圖20180906111338.png
  
  此時(shí)實(shí)現(xiàn)了第一次的翻轉(zhuǎn) 并且向上返回。

• 第二次返回

  • 返回后returnNode=6-5 returnNode= 4-5（因?yàn)樯弦淮我褜?的next置為null）
  • 然后設(shè)置currentNode.getNext().setNext(currentNode);

  • currentNode.setNext(null);

    
    
    TIM截圖20180906113058.png

• 以此類推

3 反轉(zhuǎn)的方法--遍歷反轉(zhuǎn)法

• 遍歷反轉(zhuǎn)法是從前往后反轉(zhuǎn)各個(gè)結(jié)點(diǎn)的指針域的指向

    //思路：
    //當(dāng)前節(jié)點(diǎn)的next不為null，則需要進(jìn)行反轉(zhuǎn)
    //反轉(zhuǎn)即：需要將next的next設(shè)置為當(dāng)前節(jié)點(diǎn)

    public static Node cycleReverse(Node currentNode) {

        if (currentNode == null) {
            return currentNode;
        }

        //專門記錄下一個(gè)節(jié)點(diǎn)（依次判斷下個(gè)節(jié)點(diǎn)是否為空）
        Node nextNode = currentNode.getNext();

        //記錄next的next用于下次循環(huán)使用
        Node temp;

        //準(zhǔn)備好第一個(gè)節(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)不需要去反轉(zhuǎn)）
        currentNode.setNext(null);
        Node finalNode = currentNode;//最終返回的鏈表

        //如果下一個(gè)幾點(diǎn)不為空，說明還有節(jié)點(diǎn)，則進(jìn)行反轉(zhuǎn)
        while (nextNode != null) {
            //記錄元素，為了指針下移
            temp = nextNode.getNext();

            //反轉(zhuǎn)鏈表
            nextNode.setNext(finalNode);
            finalNode = nextNode;

            //指針下移
            nextNode = temp;
        }

        return finalNode;
    }

參考

Java單鏈表反轉(zhuǎn) 詳細(xì)過程