算法例子:反轉單向連結清單(Java)

文章目錄

• • 反轉單向連結清單
  • • 1.思路
    • 2.建立連結清單節點
    • 3.建立單向連結清單
    • 4.反轉連結清單
    • 5.列印連結清單
    • 6.調用示例
    • 7.列印結果
    • 8.總結

反轉單向連結清單

1.思路

因為一個連結清單是一個單向的,如果要反轉,肯定是要周遊的,并且使連結清單使反轉.可以在新的連結清單中使用頭插入法,那麼新連結清單和原連結清單順序是逆向的.達到反轉效果.

反轉連結清單方法:reverseLinkList(Node head)

2.建立連結清單節點

public class Node {
    public int value;//連結清單的值
    public Node next;//下一節點

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }
}
           

3.建立單向連結清單

/**
     * 建立一個連結清單
     *
     * @return 傳回連結清單的頭節點
     */
    public static Node createLinkList() {

        Node header = null;
        Node h = null;
        //使用未插入法模拟建立一個連結清單
        Node node;
        for (int i = 0; i < 10; i++) {
            node = new Node(i);
            node.next = null;
            if (header == null) {
                header = node;
                h = node;
            } else {
                h.next = node;
                h = node;
            }
        }

        return header;
    }
           

0->1->2->3->4->5->6->7->8->9

4.反轉連結清單

/**
     * 反轉一個連結清單:使用頭插入法
     *
     * @param head 需要反轉的連結清單
     * @return 反轉後的連結清單
     */
    public static Node reverseLinkList(Node head) {
        Node newHead = null;
        Node temp;
        while (head != null) {
            //1.建立一個新節點,将值給你新的結點
            temp = new Node();
            temp.value = head.value;
            //2.将新結點的next指向新連結清單的頭結點
            temp.next = newHead;
            //3.将新連結清單的頭結點指向新插入的結點
            newHead = temp;
            //4.将周遊的結點指向下一結點
            head = head.next;
        }
        return newHead;
    }
           

5.列印連結清單

/**
     * 列印連結清單
     *
     * @param node
     */
    public static void printLinkList(Node node) {
        Node temp = node;
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        boolean isFlag = false;
        while (temp != null) {
            if (isFlag) {
                stringBuilder.append("->").append(temp.value);
            } else {
                stringBuilder.append(temp.value);
                isFlag = true;
            }
            temp = temp.next;
        }
        stringBuilder.append("]");
        System.out.println(stringBuilder.toString());
    }
           

6.調用示例

public static void main(String[] args) {
        System.out.println("-----\n");

        Node head = createLinkList();
        System.out.print("反轉前:");
        printLinkList(head);
        //反轉
        Node reserver = reverseLinkList(head);
        System.out.print("反轉後:");
        printLinkList(reserver);

        System.out.println("\n-----");
    }
           

7.列印結果

反轉前:[0->1->2->3->4->5->6->7->8->9]
反轉後:[9->8->7->6->5->4->3->2->1->0]
           

8.總結

本質就是利用了頭插入方法插傳入連結條,正好可以實作鍊條逆向.

了解單連結清單的操作,請檢視