java實(shí)現(xiàn)鏈表反轉(zhuǎn)
本文為大家分享了java實(shí)現(xiàn)鏈表反轉(zhuǎn)的具體代碼,供大家參考,具體內(nèi)容如下
算法題:實(shí)現(xiàn)鏈表的反轉(zhuǎn)
提供了2種方法,迭代法、遞歸法。
(為了方便輸出可視化,在自定義的ListNode中重寫了toString方法。)
/** * Created By --- on 2021/8/12 * 以下代碼可以直接粘貼進(jìn)編譯器輸出 */ public class ReverseList { public static void main(String[] args) { ListNode head = new ListNode(3, new ListNode(5, new ListNode(8, new ListNode(9)))); System.out.println("初始鏈表:" + head); ListNode newList = reverseList(head); System.out.println("使用迭代法反轉(zhuǎn)鏈表:" + newList); ListNode newList2 = reverseList2(null, newList); System.out.println("使用遞歸法反轉(zhuǎn)鏈表:" + newList2); } /** * 迭代法 */ public static ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; ListNode tmp; while (cur != null) { tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } /** * 遞歸法 */ public static ListNode reverseList2(ListNode pre, ListNode cur) { if (cur == null) { return pre; } ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; return reverseList2(pre, cur); } } /** * singly-linked list */ class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } @Override public String toString() { StringBuilder sb = new StringBuilder(String.valueOf(val)); ListNode next = this.next; while (next != null) { sb.append(next.val); next = next.next; } return sb.toString(); } }
輸出結(jié)果:
再為大家分享一段java實(shí)現(xiàn)鏈表反轉(zhuǎn)的三種方式
分別通過棧、遞歸、指針的方式實(shí)現(xiàn):
import java.util.Stack; public class ReverseLinkedList { public static void main(String[] args) { ReverseLinkedList reverseLinkedList = new ReverseLinkedList(); reverseLinkedList.test(); } public void test() { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); node1.setNext(node2); node2.setNext(node3); //方法需要替換 node1 = reverseByPointer(node1); while (node1 != null) { System.out.println(node1.val); node1 = node1.getNext(); } } //棧實(shí)現(xiàn) private Node reverseByStack(Node head) { if (head == null || head.getNext() == null) { return head; } Stack<Node> stack = new Stack<>(); while (head != null) { stack.push(head); head = head.getNext(); } head = stack.pop(); Node tmp = head; while (!stack.empty()) { Node node = stack.pop(); node.setNext(null); tmp.setNext(node); tmp = node; } return head; } //遞歸實(shí)現(xiàn) private Node reverseByRecursion(Node head) { if (head == null || head.getNext() == null) { return head; } //遞歸獲取當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn) Node tmp = reverseByRecursion(head.getNext()); Node node = head.getNext(); head.setNext(null); node.setNext(head); return tmp; } //指針實(shí)現(xiàn) private Node reverseByPointer(Node head) { if (head == null || head.getNext() == null) { return head; } //pre指針指向前一個(gè)節(jié)點(diǎn),初始第一個(gè)節(jié)點(diǎn)的前節(jié)點(diǎn)為空 Node pre = null; //tmp指針指向當(dāng)前節(jié)點(diǎn) Node tmp = null; while (head != null) { //tmp指針指向head頭指針節(jié)點(diǎn) tmp = head; //head頭指針向后遍歷 head = head.getNext(); //反轉(zhuǎn),設(shè)置當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為前一個(gè)節(jié)點(diǎn) tmp.setNext(pre); //pre指針向后移動(dòng),指向當(dāng)前節(jié)點(diǎn) pre = tmp; } return tmp; } private class Node { private int val; private Node next; public Node(int val) { this.val = val; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } }
以上就是本文的全部內(nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
Eclipse中安裝反編譯工具Fernflower的方法(Enhanced Class Decompiler)
這篇文章主要介紹了Eclipse中安裝反編譯工具Fernflower的方法(Enhanced Class Decompiler),本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-01-01SWT(JFace) 圖片瀏覽器 實(shí)現(xiàn)代碼
SWT(JFace)小制作:圖片瀏覽器2009-06-06java 輸入3個(gè)數(shù)a,b,c,按大小順序輸出的實(shí)例講解
今天小編就為大家分享一篇java 輸入3個(gè)數(shù)a,b,c,按大小順序輸出的實(shí)例講解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-07-07