問題：

實現單鏈表反轉

答案：

鏈表準備

class Node {private int Data;// 數據域private Node Next;// 指針域public Node(int Data) {// super();this.Data = Data;}public int getData() {return Data;}public void setData(int Data) {this.Data = Data;}public Node getNext() {return Next;}public void setNext(Node Next) {this.Next = Next;} } public static void main(String[] args) {Node head = new Node(0);Node node1 = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);head.setNext(node1);node1.setNext(node2);node2.setNext(node3);// 打印反轉前的鏈表Node h = head;while (null != h) {System.out.print(h.getData() + " ");h = h.getNext();}// 調用反轉方法head = reverse(head);System.out.println("\n**************************");// 打印反轉后的結果while (null != head) {System.out.print(head.getData() + " ");head = head.getNext();}}

遞歸反轉法：在反轉當前節點之前先反轉后續節點。這樣從頭結點開始，層層深入直到尾結點才開始反轉指針域的指向。簡單的說就是從尾結點開始，逆向反轉各個結點的指針域指向

private static Node reverse1(Node head) {if(head==null||head.getNext()==null){return head;}Node reHead = reverse1(head.getNext());head.getNext().setNext(head);head.setNext(null);return reHead;}

?

遍歷反轉法：遞歸反轉法是從后往前逆序反轉指針域的指向，而遍歷反轉法是從前往后反轉各個結點的指針域的指向

private static Node reverse2(Node head) {if(head==null){return head;}Node pre = head;Node cur = head.getNext();Node temp;while (cur!=null) {temp = cur.getNext();cur.setNext(pre);pre = cur;cur=temp;}head.setNext(null);return pre;}

?

?

?

?

?

總結

以上是生活随笔為你收集整理的【算法系列之三】单链表反转的全部內容，希望文章能夠幫你解決所遇到的問題。

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