思路

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

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

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

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

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

需要注意的是 如果鏈表一開(kāi)始就是空的，直接返回 null即可，因?yàn)榭盏逆湵頍o(wú)法反轉(zhuǎn)。如果此時(shí)的鏈表只有一個(gè)結(jié)點(diǎn)，也不需要反轉(zhuǎn)，因?yàn)橐粋€(gè)結(jié)點(diǎn)再怎么反轉(zhuǎn)也沒(méi)有變化。

核心四步驟

核心四步驟分別是 ：

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

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

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

此時(shí)第一個(gè)結(jié)點(diǎn)就已經(jīng)移動(dòng)完成了，但是會(huì)發(fā)現(xiàn)如果還想要移動(dòng)其他的結(jié)點(diǎn)的話其實(shí)是無(wú)法實(shí)現(xiàn)了。
因?yàn)榇藭r(shí)原本的 head 結(jié)點(diǎn)早與后面的結(jié)點(diǎn)斷開(kāi)了連接，此時(shí)是無(wú)法操作后面剩余結(jié)點(diǎn)的。

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

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

可以看到此時(shí) curNext 就指向了 cur 結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。

接下來(lái)就是更改 cur 結(jié)點(diǎn)的指向，將它移動(dòng)到 head 結(jié)點(diǎn)的前面。

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

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

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

循環(huán)移動(dòng)

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

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

代碼實(shí)現(xiàn)

class MySingleNodeTest {
    static class ListNode{
        public int value;//數(shù)據(jù)
        public ListNode next;//地址
        public ListNode(int value) {
            this.value = value;
        }
    }
    //設(shè)置頭結(jié)點(diǎn)
    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é)點(diǎn)
    }
    // 打印鏈表
    public void disPlay() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;//cur指向它的下一個(gè)
        }
        System.out.println();//換行
    }
    // 反轉(zhuǎn)一個(gè)鏈表
    public ListNode reversalList() {
        // 如果鏈表是空的
        if (this.head == null) {
            return null;
        }
        // 如果只有一個(gè)結(jié)點(diǎn)不需要反轉(zhuǎn)
        if (this.head.next == null) {
            return this.head;
        }
        // 創(chuàng)建一個(gè) cur 指向頭結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)
        ListNode cur = this.head.next;
        // 將頭結(jié)點(diǎn)置為空
        this.head.next = null;
        // 開(kāi)始四個(gè)步驟移動(dòng) cur 和后面的結(jié)點(diǎn)
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = this.head;
            head = cur;
            cur = curNext;
        }
        // 循環(huán)結(jié)束反轉(zhuǎn)完成返回頭結(jié)點(diǎn)即可
        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)之前情況：

可以看到此時(shí) 頭結(jié)點(diǎn) 中的數(shù)據(jù)是 12，而末尾結(jié)點(diǎn)中的數(shù)據(jù)是 45。此時(shí)對(duì)應(yīng)的鏈表圖解如下圖：

(2) 反轉(zhuǎn)之后的情況：

調(diào)用反轉(zhuǎn)方法后，可以看到此時(shí)頭結(jié)點(diǎn)中的數(shù)據(jù)變成了 45，而尾結(jié)點(diǎn)變成了 12。此時(shí)說(shuō)明反轉(zhuǎn)成功了。此時(shí)對(duì)應(yīng)的鏈表圖解如下圖：

 到此這篇關(guān)于Java實(shí)現(xiàn)反轉(zhuǎn)一個(gè)鏈表的示例代碼的文章就介紹到這了,更多相關(guān)Java 反轉(zhuǎn)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論