快捷導(dǎo)航

Java反轉(zhuǎn)鏈表測試過程介紹

更新時間：2023年04月12日 11:26:41 作者：ziop-三月

這篇文章主要介紹了Java反轉(zhuǎn)鏈表測試過程，學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)的小伙伴們，對鏈表想來是并不陌生。本篇文章將為大家介紹幾種在Java語言當(dāng)中，實現(xiàn)鏈表反轉(zhuǎn)的幾種方法，以下是具體內(nèi)容

導(dǎo)讀

本文主體為單項鏈表和雙向鏈表的反轉(zhuǎn)以及簡單的測試，以便于理解鏈表相關(guān)的算法題目。

鏈表

特點

便于增刪數(shù)據(jù)，不便于尋址
在內(nèi)存中屬于跳轉(zhuǎn)結(jié)構(gòu)

單鏈表和雙鏈表的定義

單鏈表：值，一條next指針

雙鏈表：值，一條last指針，一條next指針

單向鏈表

Node結(jié)點

public static class Node {
    public int value;
    public Node next;
    public Node(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        ArrayList<Integer> nums = new ArrayList<>();
        Node node = this;
        while (node != null) {
            nums.add(node.value);
            node = node.next;
        }
        return nums.toString();
    }
}

反轉(zhuǎn)單向鏈表

public static Node reverseLinkedList(Node head) {
    Node next = null;
    Node pre = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

測試函數(shù)

public static void main(String[] args) {
    Node node = new Node(1);
    node.next = new Node(2);
    node.next.next = new Node(3);
    node = reverseLinkedList(node);
    System.out.println(node);
}

輸出結(jié)果如下：

[3, 2, 1]

雙向鏈表

Node結(jié)點

public static class DoubleList {
    public int value;
    public DoubleList next;
    public DoubleList last;
    public DoubleList(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        ArrayList<Integer> nums = new ArrayList<>();
        DoubleList node = this;
        while (node != null) {
            nums.add(node.value);
            node = node.next;
        }
        return nums.toString();
    }
}

反轉(zhuǎn)雙向鏈表

public static DoubleList reverseDoubleList(DoubleList head) {
    DoubleList next;
    DoubleList pre = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        // 注意和單項鏈表不一樣的地方只有這一行，其他都基本一樣
        head.last = next;
        pre = head;
        head = next;
    }
    return pre;
}

測試代碼

public static void main(String[] args) {
    DoubleList node1 = new DoubleList(1);
    node1.next = new DoubleList(2);
    node1.next.last = node1;
    node1.next.next = new DoubleList(3);
    node1.next.next.last = node1.next;
    System.out.println("reverseDoubleList(node1) = " + reverseDoubleList(node1));
}

輸出結(jié)果如下：