您好,登錄后才能下訂單哦!
這篇文章主要講解了“Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎn)”吧!
import java.util.ArrayList; import java.util.Stack; /** * 鏈表的反轉(zhuǎn) */ public class ReverseLinkedList { /** * 非遞歸地反轉(zhuǎn)鏈表: * * 特點(diǎn):沒有進(jìn)行節(jié)點(diǎn)間的兩兩反轉(zhuǎn),而是采用依次插入到新鏈表的方式來實(shí)現(xiàn)反轉(zhuǎn)。 * * 過程:遍歷一次鏈表,將遍歷的節(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)暫存起來 /** * 將當(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)。 * * 過程:遞歸地將當(dāng)前節(jié)點(diǎn)(current)和它的后繼節(jié)點(diǎn)(current.next)反轉(zhuǎn)。 * * 注意: * 1)最后一個(gè)節(jié)點(diǎn)沒有后繼節(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í),開始第一次的反轉(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)放到新鏈表的尾部,故在遞歸的過程中新鏈表的頭部不會(huì)變。 current.next.next = current; current.next = null; // 將新鏈表的頭節(jié)點(diǎn)返回。 return newHead; } // ------- /** * 利用棧的先進(jìn)后出特性來完成鏈表的反轉(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)暫存起來 current.next = current.prev; current.prev = next; if (null == next) { // 若下一個(gè)要遍歷的節(jié)點(diǎn)為null,則說明已經(jīng)到達(dá)鏈表的尾部,此時(shí)current即鏈表的尾節(jié)點(diǎn) newHead = current; } current = next; // 繼續(xù)向后遍歷 } return newHead; } // ------- /** * 將鏈表從頭到尾依次打印出來 * * @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()); } /** * 將雙向鏈表從尾到頭依次打印出來 * * @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)過本文的學(xué)習(xí)后,相信大家對(duì)Java怎么實(shí)現(xiàn)鏈表的反轉(zhuǎ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)容。