單鏈表逆轉置的遞歸與非遞歸方式

package link.reverse; // 定義一個單鏈表 class Node { //變量 private int record; //指向下一個對象 private Node nextNode; public Node(int record) { this.record = record; } public int getRecord() { return record; } public void setRecord(int record) { this.record = record; } public Node getNextNode() { return nextNode; } public void setNextNode(Node nextNode) { this.nextNode = nextNode; } } /** * 兩種方式實現單鏈表的反轉(遞歸、普通) */ public class RevSingleLinkFactory { /** * 遞歸，在反轉當前節點之前先反轉后續節點 */ //最終傳遞一個指向最后一個節點的變量public static Node reverse1(Node head) { //當為空或者本節點為末尾節點的時候if (head ==null ||head.getNextNode()==null) return head; Node reversedHead = reverse1(head.getNextNode());//獲取先前的下一個節點，讓該節點指向自身head.getNextNode().setNextNode(head); //破壞以前自己指向下一個節點head.setNextNode(null); //層層傳遞給最上面的return reversedHead; } /** * 遍歷，將當前節點的下一個節點緩存后更改當前節點指針 */ public static Node reverse2(Node head) { if (null == head) { return head; } Node pre = head; Node cur = head.getNextNode(); Node next; while (cur !=null) {//斷之前先找到原始的下一個節點next = cur.getNextNode(); //逆序連接cur.setNextNode(pre); //兩個節點同時滑動pre = cur; cur = next; } //將原鏈表的頭節點的下一個節點置為null，再將反轉后的頭節點賦給head head.setNextNode(null); head = pre; return head; } public static void main(String[] args) { //帶有頭結點Node head = new Node(0); Node tmp = null; // 保存臨時變量Node cur = null; // 始終指向末尾節點//構造一個長度為10的鏈表，保存頭節點對象head //利用尾插入法for (int i = 1; i < 10; i++) { tmp = new Node(i); if (1 == i) { head.setNextNode(tmp); } else { cur.setNextNode(tmp); } cur = tmp; } //打印反轉前的鏈表 Node h = head; while (h !=null) { System.out.print(h.getRecord() + " "); h = h.getNextNode(); } //調用反轉方法 head = reverse1(head); System.out.println("\n*******************"); //打印反轉后的結果 while (head !=null) { System.out.print(head.getRecord() + " "); head = head.getNextNode(); } } }

轉載于:https://blog.51cto.com/computerdragon/1305986

總結

以上是生活随笔為你收集整理的Java实现单链表的逆转置的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。