Java 反轉連結清單的兩種方法

目錄

• 目錄
• 連結清單節點的資料結構
• 方法一周遊
• 方法二遞歸

連結清單節點的資料結構

• 連結清單的資料結構主要是由兩部分組成的，顯而易見，一個就是目前的節點存儲的資料，一個就是指向下一個節點。

/**
 * 連結清單的節點
 * 
 * @author yingmu
 *
 */
public class Node {
    private char Data;// 資料域  
    private Node Next;// 指針域  
    public Node(char Data) {  
        // super();  
        this.Data = Data;  
    }  
    public char getData() {  
        return Data;  
    }  
    public void setData(char Data) {  
        this.Data = Data;  
    }  

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

方法一：周遊

/**
* 周遊方法
* 
* @param current
* @return
* 
*/
public static Node reverseList2(Node head) {
    if (head == null)  
        return head;  

    Node pre = head;// 上一結點  
    Node cur = head.getNext();// 目前結點  
    Node tmp;// 臨時結點，用于儲存目前結點的指針域（即下一結點）  
    while (cur != null) {// 目前結點為null，說明位于尾結點  
            tmp = cur.getNext();  
            cur.setNext(pre);// 反轉指針域的指向  

            // 指針往下移動  
            pre = cur;  
            cur = tmp;  
    }  
    // 最後将原連結清單的頭節點的指針域置為null，還回新連結清單的頭結點，即原連結清單的尾結點  
    head.setNext(null);          
    return pre;  
}
           

方法二：遞歸

/**
* 遞歸，在反轉目前節點之前先反轉後續節點 
* 
* @param head
* @return
* 
*/
public static Node reverseList1(Node head) {
       // head看作是前一結點，head.getNext()是目前結點，reHead是反轉後新連結清單的頭結點  
       if (head == null || head.getNext() == null) {  
            return head;// 若為空鍊或者目前結點在尾結點，則直接還回  
        }  
        Node reHead = reverseList1(head.getNext());// 先反轉後續節點head.getNext()  
        head.getNext().setNext(head);// 将目前結點的指針域指向前一結點  
        head.setNext(null);// 前一結點的指針域令為null;  
        return reHead;// 反轉後新連結清單的頭結點  
}
           

• 源代碼位址