免费观看又色又爽又黄的小说免费_美女福利视频国产片_亚洲欧美精品_美国一级大黄大色毛片

Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)

這篇文章主要講解了“Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)”吧！

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括環(huán)縣網(wǎng)站建設(shè)、環(huán)縣網(wǎng)站制作、環(huán)縣網(wǎng)頁(yè)制作以及環(huán)縣網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，環(huán)縣網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到環(huán)縣省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

import java.util.ArrayList;
import java.util.Stack;

    /**
     * 鏈表的反轉(zhuǎn)
     */
public class ReverseLinkedList {

/**
 * 非遞歸地反轉(zhuǎn)鏈表：
 *
 *  特點(diǎn)：沒(méi)有進(jìn)行節(jié)點(diǎn)間的兩兩反轉(zhuǎn)，而是采用依次插入到新鏈表的方式來(lái)實(shí)現(xiàn)反轉(zhuǎn)。
 *
 *  過(guò)程：遍歷一次鏈表，將遍歷的節(jié)點(diǎn)依次插入到新鏈表的頭部即可實(shí)現(xiàn)鏈表的反轉(zhuǎn)。
 *
 *  復(fù)雜度：時(shí)間復(fù)雜度為O(N),輔助的空間復(fù)雜度為O(1)
 *
 * [@param](https://my.oschina.net/u/2303379) head
 *
 * [@return](https://my.oschina.net/u/556800) 將反轉(zhuǎn)后的新鏈表的頭節(jié)點(diǎn)返回。
 */
public static Node reverseByInsertToNewList(Node head) {

    Node current = head; // 正在遍歷的節(jié)點(diǎn)
    Node next = null;    // 下一個(gè)要遍歷的節(jié)點(diǎn)
    Node newHead = null; // 新鏈表頭節(jié)點(diǎn)的引用(指向新鏈表頭節(jié)點(diǎn)的指針)

    while (null != current) {

        next = current.next; // 將下一個(gè)要遍歷的節(jié)點(diǎn)暫存起來(lái)

        /**
         * 將當(dāng)前節(jié)點(diǎn)放到新鏈表的頭部：
         *    1>將當(dāng)前節(jié)點(diǎn)指向新鏈表的頭部
         *    2>更新newHead
         */
        current.next = newHead;
        newHead = current;

        current = next; // 向后繼續(xù)遍歷
    }

    return newHead;
}


/**
 * 遞歸地反轉(zhuǎn)鏈表：
 *
 *  特點(diǎn)：從后往前兩兩反轉(zhuǎn)。
 *
 *  過(guò)程：遞歸地將當(dāng)前節(jié)點(diǎn)(current)和它的后繼節(jié)點(diǎn)(current.next)反轉(zhuǎn)。
 *
 *  注意：
 *      1)最后一個(gè)節(jié)點(diǎn)沒(méi)有后繼節(jié)點(diǎn)，故最后一個(gè)節(jié)點(diǎn)不需要進(jìn)行反轉(zhuǎn)操作，只需將最后一個(gè)節(jié)點(diǎn)(作為新鏈表的頭節(jié)點(diǎn))直接返回即可。
 *      2)當(dāng)前節(jié)點(diǎn)為鏈表倒數(shù)第二個(gè)節(jié)點(diǎn)時(shí)，開(kāi)始第一次的反轉(zhuǎn)操作。
 *      3)每次的反轉(zhuǎn)操作都不會(huì)對(duì)新鏈表的頭節(jié)點(diǎn)造成影響，只是將新的頭結(jié)點(diǎn)返回而已。
 *
 *  解析：
 *      1)將 A->B->C->D 反轉(zhuǎn)的操作可以分為：
 *          1>將 C->D 反轉(zhuǎn) ==> A->B->C  D->C->null
 *          2>將 B->C 反轉(zhuǎn) ==> A->B     D->C->B->null
 *          3>將 A->B 反轉(zhuǎn) ==>          D->C->B->A->null
 *
 *      2)將 A->B 反轉(zhuǎn)的操作：
 *          1>將B的后繼節(jié)點(diǎn)指向A，      即 B.next = A    即 A.next.next = A
 *          2>將A的后繼節(jié)點(diǎn)設(shè)為null，   即 A.next = null
 *
 * [@param](https://my.oschina.net/u/2303379) current
 *
 * [@return](https://my.oschina.net/u/556800) 將反轉(zhuǎn)后的新鏈表的頭節(jié)點(diǎn)返回。
 */
private static Node reverseByRecursion(Node current) {

    if (null == current) {      // 若該鏈表為空鏈表，則直接返回
        return current;
    }

    if (null == current.next) { // 當(dāng)前結(jié)點(diǎn)是尾結(jié)點(diǎn)時(shí)，直接返回。注：鏈表的尾節(jié)點(diǎn)即新鏈表的頭節(jié)點(diǎn)
        return current;
    }

    Node newHead = reverseByRecursion(current.next); // newHead是鏈表的尾節(jié)點(diǎn)，即新鏈表的頭節(jié)點(diǎn)。

    // 反轉(zhuǎn)操作：將current和current.next進(jìn)行反轉(zhuǎn)，即：將當(dāng)前節(jié)點(diǎn)放到新鏈表的尾部，故在遞歸的過(guò)程中新鏈表的頭部不會(huì)變。
    current.next.next = current;
    current.next = null;

    // 將新鏈表的頭節(jié)點(diǎn)返回。
    return newHead;
}


// -------

/**
 * 利用棧的先進(jìn)后出特性來(lái)完成鏈表的反轉(zhuǎn)。
 *
 * 時(shí)間復(fù)雜度為O(N),輔助的空間復(fù)雜度也為O(N)
 *
 * [@param](https://my.oschina.net/u/2303379) head
 * @return 將反轉(zhuǎn)后的新鏈表的頭節(jié)點(diǎn)返回。
 */
public static Node reverseWithStack(Node head) {

    Stack<Node> stack = new Stack<Node>();
    while (null != head) {
        stack.push(head);
        head = head.next;
    }
    return stack.peek();
}


/**
 * 反轉(zhuǎn)雙向鏈表
 *
 *  復(fù)雜度：時(shí)間復(fù)雜度為O(N),輔助的空間復(fù)雜度為O(1)
 *
 * @param head
 * @return 將反轉(zhuǎn)后的新鏈表的頭節(jié)點(diǎn)返回。
 */
public static Node reverseBidirectionalList(Node head) {

    if (null == head) { // 若該鏈表為空鏈表，則直接返回
        return null;
    }

    Node current = head;
    Node next = null;
    Node newHead = null;

    while (null != current) {

        // 反轉(zhuǎn)
        next = current.next;    // 將當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)暫存起來(lái)
        current.next = current.prev;
        current.prev = next;

        if (null == next) {     // 若下一個(gè)要遍歷的節(jié)點(diǎn)為null，則說(shuō)明已經(jīng)到達(dá)鏈表的尾部，此時(shí)current即鏈表的尾節(jié)點(diǎn)
            newHead = current;
        }

        current = next;         // 繼續(xù)向后遍歷
    }

    return newHead;
}


// -------

/**
 * 將鏈表從頭到尾依次打印出來(lái)
 *
 * @param head
 */
public static void print(Node head) {

    ArrayList<Object> list = new ArrayList<>();
    while (null != head.next) {
        list.add(head.value);
        head = head.next;
    }
    list.add(head.value);
    System.out.println(list.toString());
}

/**
 * 將雙向鏈表從尾到頭依次打印出來(lái)
 *
 * @param tail
 */
public static void printBidirectionList(Node tail) {

    ArrayList<Object> list = new ArrayList<>();
    while (null != tail.prev) {
        list.add(tail.value);
        tail = tail.prev;
    }
    list.add(tail.value);
    System.out.println(list.toString());
}

/**
 * 初始化鏈表
 *
 * @return
 */
public static Node init() {

    Node head = new Node(5);
    Node node1 = new Node(3);
    Node node2 = new Node(2);
    Node node3 = new Node(6);
    Node node4 = new Node(7);
    Node node5 = new Node(17);
    Node node6 = new Node(9);

    head.next = node1;

    node1.prev = head;
    node1.next = node2;

    node2.prev = node1;
    node2.next = node3;

    node3.prev = node2;
    node3.next = node4;

    node4.prev = node3;
    node4.next = node5;

    node5.prev = node4;
    node5.next = node6;

    node6.prev = node5;
    node6.next = null;
    return head;
}


public static void main(String[] args) {

    Node head = init();
    print(head);

    // 反轉(zhuǎn)單向鏈表
//        Node newHead = reverseByInsertToNewList(head);
//        Node newHead = reverseByRecursion(head);

    // 反轉(zhuǎn)雙向鏈表
    Node newHead = reverseBidirectionalList(head);

    print(newHead);

    // 利用stack反轉(zhuǎn)雙向鏈表
    Node newHeadByStack = reverseWithStack(head);
    printBidirectionList(newHeadByStack);

}

感謝各位的閱讀，以上就是“Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

分享標(biāo)題：Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)
分享網(wǎng)址：http://m.newbst.com/article40/gpjgho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、響應(yīng)式網(wǎng)站、微信公眾號(hào)、動(dòng)態(tài)網(wǎng)站、軟件開(kāi)發(fā)、小程序開(kāi)發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

商城網(wǎng)站建設(shè)