快捷導航

Java實現(xiàn)反轉(zhuǎn)一個鏈表的示例代碼

更新時間：2023年07月04日 16:07:39 作者：與大師約會

本文主要介紹了Java實現(xiàn)反轉(zhuǎn)一個鏈表的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

思路

翻轉(zhuǎn)指的是改變鏈表中結(jié)點的指向，而不是將它的數(shù)據(jù)反轉(zhuǎn)。

上圖展示出的就是一個反轉(zhuǎn)前的鏈表，下圖展示一個反轉(zhuǎn)后的鏈表。

根據(jù)上圖可以看出，結(jié)點的地址和數(shù)據(jù)都沒有改變，改變的只是鏈表結(jié)點的指向，更改后的頭結(jié)點變成了尾結(jié)點。首先要定義一個 cur 變量，讓這個變量指向 head 結(jié)點 的下一個結(jié)點。接著就是將 head 結(jié)點置為空，也就是將 head 結(jié)點地址域保存的地址改為 null 即可。

鏈表中的 head 結(jié)點原本保存的是 0x11 這個地址，但是現(xiàn)在改為了 null，表示與后面的結(jié)點斷開了連接。

cur 這個變量指向的就是 head 結(jié)點的下一個結(jié)點，由于 head 結(jié)點地址域里保存的地址改為 null 就與后面結(jié)點斷開連接了，此時為了保證 cur 可以成功指向，因此需要先將 cur 移動，然后再改 head 結(jié)點的地址域。接下來要做的就是將 cur 指向的結(jié)點和它后面的結(jié)點全部移動到 head 結(jié)點前面即可。

需要注意的是 如果鏈表一開始就是空的，直接返回 null即可，因為空的鏈表無法反轉(zhuǎn)。如果此時的鏈表只有一個結(jié)點，也不需要反轉(zhuǎn)，因為一個結(jié)點再怎么反轉(zhuǎn)也沒有變化。

核心四步驟

核心四步驟分別是：

1.curNext = cur.next
2.cur.next = head
3.head = cur
4.cur = curNext

先定義的 curNext 始終指向 cur.next，curNext 是為了保證將所有的結(jié)點都移動到 head 結(jié)點的前面去，實現(xiàn)的一個類似于記錄的功能。

先將 cur 結(jié)點移動到 head 結(jié)點的前面，只需要更改 cur 結(jié)點地址域中的保存的地址即可，
接著是將 head 指向 cur 指向的結(jié)點。

此時第一個結(jié)點就已經(jīng)移動完成了，但是會發(fā)現(xiàn)如果還想要移動其他的結(jié)點的話其實是無法實現(xiàn)了。
因為此時原本的 head 結(jié)點早與后面的結(jié)點斷開了連接，此時是無法操作后面剩余結(jié)點的。

此時四個核心步驟中的第一個和第四個就體現(xiàn)出了作用。

首先將定義好的 curNext 指向并且始終指向 cur 結(jié)點的下一個結(jié)點。

可以看到此時 curNext 就指向了 cur 結(jié)點的下一個結(jié)點。

接下來就是更改 cur 結(jié)點的指向，將它移動到 head 結(jié)點的前面。

然后是將 head 指向 cur 指向的位置。

此時當我們打算移動其它結(jié)點的時候會發(fā)現(xiàn)，只需要將 cur 指向 curNext 即可訪問到其他的結(jié)點了。這也就是和心步驟的第四步 cur = curNext。

以上過程是把這四個步驟都走了一遍才會產(chǎn)生的結(jié)果，想要把所有的結(jié)點都移動到完畢，繼續(xù)按照順序執(zhí)行上面的四個步驟即可。

循環(huán)移動

想要將所有的結(jié)點全部移動完畢，實現(xiàn)一個循環(huán)即可，在這個循環(huán)里面去重復執(zhí)行上述的四個步驟。

當重復執(zhí)行了幾次循環(huán)之后，會發(fā)現(xiàn)此時的 cur 雖仍然是指向了 curNext，但是此時 cur 是為空的。我們此時又可以發(fā)現(xiàn)，鏈表已經(jīng)反轉(zhuǎn)完成了，因此循環(huán)的判定條件就是當 cur 不為空時就繼續(xù)執(zhí)行循環(huán)，若 cur 為空，也就是說明此時的鏈表已經(jīng)反轉(zhuǎn)成功了，跳出循環(huán)返回當前的 head 即可。

代碼實現(xiàn)

class MySingleNodeTest {
    static class ListNode{
        public int value;//數(shù)據(jù)
        public ListNode next;//地址
        public ListNode(int value) {
            this.value = value;
        }
    }
    //設(shè)置頭結(jié)點
    public ListNode head;
    //創(chuàng)建鏈表
    public void createNode() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        this.head = listNode1;//設(shè)置頭結(jié)點
    }
    // 打印鏈表
    public void disPlay() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;//cur指向它的下一個
        }
        System.out.println();//換行
    }
    // 反轉(zhuǎn)一個鏈表
    public ListNode reversalList() {
        // 如果鏈表是空的
        if (this.head == null) {
            return null;
        }
        // 如果只有一個結(jié)點不需要反轉(zhuǎn)
        if (this.head.next == null) {
            return this.head;
        }
        // 創(chuàng)建一個 cur 指向頭結(jié)點的后一個結(jié)點
        ListNode cur = this.head.next;
        // 將頭結(jié)點置為空
        this.head.next = null;
        // 開始四個步驟移動 cur 和后面的結(jié)點
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = this.head;
            head = cur;
            cur = curNext;
        }
        // 循環(huán)結(jié)束反轉(zhuǎn)完成返回頭結(jié)點即可
        return this.head;
    }
}
public class MySingleNode {
    public static void main(String[] args) {
        MySingleNodeTest mySingleNodeTest = new MySingleNodeTest();
        // 調(diào)用方法創(chuàng)建鏈表
        mySingleNodeTest.createNode();
        // 打印反轉(zhuǎn)之前的鏈表
        mySingleNodeTest.disPlay();
        // 調(diào)用反轉(zhuǎn)方法反轉(zhuǎn)
        mySingleNodeTest.reversalList();
        // 打印反轉(zhuǎn)之后的鏈表
        mySingleNodeTest.disPlay();
    }
}

(1) 反轉(zhuǎn)之前情況：