Java單鏈表反轉-有解無憂

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域，相比于線性表順序結構，操作復雜，由于不必須按順序存盤，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)，

這篇文章主要記錄一下單鏈表反轉

v定義鏈表

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class ListNode {
    public int value;
    public ListNode next;

    public ListNode(int data){
        this.value =https://www.cnblogs.com/toutou/archive/2021/09/26/ data;
    }
}

v遞回實作

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class ReverseHelper {
    public static ListNode reverse(ListNode curr){
        if(curr == null || curr.next == null){
            return curr;
        }

        ListNode temp = curr.next;
        ListNode newNode = reverse(curr.next);
        temp.next = curr;
        curr.next = null;
        return newNode;
    }
}

v非遞回實作

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class ReverseHelper {
    public static ListNode whileReverse(ListNode curr){
        ListNode pre = null;
        ListNode next = null;
        while(curr != null){
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }

        return pre;
    }
}

v測驗效果

/**
 * @author toutou https://www.cnblogs.com/toutou/
 * @date by 2020/11
 * @des
 */
public class App {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode tmp = null;
        ListNode cur = null;
        for (int i = 1; i < 10; i++) {
            tmp = new ListNode(i);
            if (1 == i) {
                head.next = tmp;
            } else {
                cur.next = tmp;
            }
            cur = tmp;
        }

        // ListNode node1 =ReverseHelper.whileReverse(head);
        ListNode node1 =ReverseHelper.reverse(head);
        while (node1!= null){
            System.out.println(node1.value);
            node1 = node1.next;
        }

        System.out.println("OK");
    }
}

v原始碼地址

https://github.com/toutouge/javademosecond/tree/master/hellospringboot

作　　者：請叫我頭頭哥
出　　處：http://www.cnblogs.com/toutou/
關于作者：專注于基礎平臺的專案開發，如有問題或建議，請多多賜教！
著作權宣告：本文著作權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段宣告，且在文章頁面明顯位置給出原文鏈接，
特此宣告：所有評論和私信都會在第一時間回復，也歡迎園子的大大們指正錯誤，共同進步，或者直接私信我
聲援博主：如果您覺得文章對您有幫助，可以點擊文章右下角【推薦】一下，您的鼓勵是作者堅持原創和持續寫作的最大動力！

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303219.html

標籤：其他

上一篇：Spring Boot MongoDB 簡單入門

下一篇：MyBatis筆記：動態SQL