您好,登錄后才能下訂單哦!
這篇文章主要講解了“Java逆轉(zhuǎn)單向鏈表怎么實(shí)現(xiàn)”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“Java逆轉(zhuǎn)單向鏈表怎么實(shí)現(xiàn)”吧!
首先這是一個(gè)單向的鏈表,不同于 Java 里面的 LinkedList,它是雙向的鏈表。鏈表中每個(gè)節(jié)點(diǎn)之間通過(guò) next 指針串接起來(lái),會(huì)有一個(gè)鏈表頭和鏈表尾指針 hold 住整個(gè)鏈表。逆轉(zhuǎn)的任務(wù)就是將 head -> a -> b -> c -> d <- tail 變成 head -> d -> c -> b -> a <- tail。
class Node<T> {
T value;
Node<T> next;
Node(T value) {
this.value = value;
}
}
class ReverseLinkedList<T> {
Node<T> head, tail;
}
我們需要將所有的元素一個(gè)一個(gè)的使用 next 指針串接起來(lái),鏈表的頭尾節(jié)點(diǎn)要用 head 和 tail 變量把持住。加入新元素時(shí),需要調(diào)整尾部節(jié)點(diǎn)的 next 指針,指向新加入的元素節(jié)點(diǎn)。
class ReverseLinkedList<T> {
private Node<T> head, tail;
public ReverseLinkedList(T... values) {
for (T value : values) {
if (tail == null) {
// 第一個(gè)節(jié)點(diǎn)
head = tail = new Node<>(value);
} else {
// 后面的節(jié)點(diǎn)往鏈表尾部追加
Node<T> oldTail = tail;
oldTail.next = tail = new Node<>(value);
}
}
}
}
ReverseLinkedList<Integer> l = new ReverseLinkedList<>(1,2,3,4,5,6);
我們需要提供一個(gè)鏈表的輸出方法,以便快速對(duì)比逆轉(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();
}
}
循環(huán)調(diào)整 next 指針是最容易想到的方法,但是要將指針精確地逆轉(zhuǎn)正確其實(shí)并不容易。下面代碼中的循環(huán)部分很短,但是卻很精致,使用了三個(gè)臨時(shí)局部變量 cur、next 和 nextnext,稍有不慎就會(huì)出錯(cuò)。
當(dāng)我寫(xiě)完下面這段代碼時(shí),雖然可以正常運(yùn)行出期望的結(jié)果,但是總當(dāng)心哪里會(huì)有遺漏,是不是什么地方少了個(gè) if else,這就是編寫(xiě)算法代碼時(shí)常見(jiàn)的心理狀態(tài)。
class ReverseLinkedList<T> {?
private Node<T> head, tail
public ReverseLinkedList<T> reverseByLoop() {
// 空鏈表或者單元素都無(wú)需處理
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;
}
}
使用遞歸的思想來(lái)解決這個(gè)問(wèn)題也是一個(gè)很好的主意,只不過(guò)當(dāng)鏈表特別長(zhǎng)時(shí),調(diào)用棧會(huì)很深,鏈表長(zhǎng)到一定程度就會(huì)拋出臭名昭著的異常 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)單向鏈表怎么實(shí)現(xiàn)”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)Java逆轉(zhuǎn)單向鏈表怎么實(shí)現(xiàn)這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。