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

創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站設(shè)計、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)與策劃設(shè)計,廬山網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:廬山等地區(qū)。廬山做網(wǎng)站價格咨詢:18980820575

首先這是一個單向的鏈表，不同于 Java 里面的 LinkedList，它是雙向的鏈表。鏈表中每個節(jié)點之間通過 next 指針串接起來，會有一個鏈表頭和鏈表尾指針 hold 住整個鏈表。逆轉(zhuǎn)的任務(wù)就是將 head -> a -> b -> c -> d <- tail 變成 head -> d -> c -> b -> a <- tail。

鏈表結(jié)構(gòu)表示

class Node<T> {
    T value;
    Node<T> next;

    Node(T value) {
        this.value = value;
    }
}

class ReverseLinkedList<T> {
  Node<T> head, tail;
}

鏈表構(gòu)造器

我們需要將所有的元素一個一個的使用 next 指針串接起來，鏈表的頭尾節(jié)點要用 head 和 tail 變量把持住。加入新元素時，需要調(diào)整尾部節(jié)點的 next 指針，指向新加入的元素節(jié)點。

class ReverseLinkedList<T> {
  private Node<T> head, tail;

  public ReverseLinkedList(T... values) {
    for (T value : values) {
        if (tail == null) {
            // 第一個節(jié)點
            head = tail = new Node<>(value);
        } else {
            // 后面的節(jié)點往鏈表尾部追加
            Node<T> oldTail = tail;
            oldTail.next = tail = new Node<>(value);
        }
    }
  }
}

ReverseLinkedList<Integer> l = new ReverseLinkedList<>(1,2,3,4,5,6);

鏈表內(nèi)容呈現(xiàn)

我們需要提供一個鏈表的輸出方法，以便快速對比逆轉(zhuǎn)后鏈表的內(nèi)容是否正確

class ReverseLinkedList<T> {
  private Node<T> head, tail;

  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    Node<T> cur = head;
    while (cur != null) {
        sb.append(cur.value);
        cur = cur.next;
        if (cur != null) {
            sb.append(',');
        }
    }
    sb.append(']');
    return sb.toString();
  }
}

迭代逆轉(zhuǎn)算法

循環(huán)調(diào)整 next 指針是最容易想到的方法，但是要將指針精確地逆轉(zhuǎn)正確其實并不容易。下面代碼中的循環(huán)部分很短，但是卻很精致，使用了三個臨時局部變量 cur、next 和 nextnext，稍有不慎就會出錯。

當(dāng)我寫完下面這段代碼時，雖然可以正常運行出期望的結(jié)果，但是總當(dāng)心哪里會有遺漏，是不是什么地方少了個 if else，這就是編寫算法代碼時常見的心理狀態(tài)。

class ReverseLinkedList<T> {?
  private Node<T> head, tail

  public ReverseLinkedList<T> reverseByLoop() {
    // 空鏈表或者單元素都無需處理
    if (head == tail) {
        return this;
    }
    Node<T> cur = head;
    Node<T> next = cur.next;
    while (next != null) {
        Node<T> nextnext = next.next;
        next.next = cur;
        cur = next;
        next = nextnext;
    }
    tail = head;
    tail.next = null;
    head = cur;
    return this;
  }
}

遞歸逆轉(zhuǎn)算法

使用遞歸的思想來解決這個問題也是一個很好的主意，只不過當(dāng)鏈表特別長時，調(diào)用棧會很深，鏈表長到一定程度就會拋出臭名昭著的異常 StackOverflowException。

class ReverseLinkedList<T> {?
  private Node<T> head, tail

  public ReverseLinkedList<T> reverseByRecursive() {
    Node<T> oldTail = tail;
    tail = reverseFrom(head);
    tail.next = null;
    head = oldTail;
    return this;
  }

  private Node<T> reverseFrom(Node<T> from) {
      if (from == tail) {
      return from;
    }
    Node<T> end = reverseFrom(from.next);
    end.next = from;
    return from;
  }
}

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

本文標(biāo)題：Java?逆轉(zhuǎn)單向鏈表怎么實現(xiàn)-創(chuàng)新互聯(lián)
鏈接URL：http://sd-ha.com/article30/jjipo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、App設(shè)計、域名注冊、品牌網(wǎng)站建設(shè)、做網(wǎng)站、網(wǎng)站導(dǎo)航

廣告

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