單鏈表逆轉置的遞歸與非遞歸方式
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();
}
}
}
