使用遞歸來反轉單鏈表需要使用兩個指針,一個用來指向當前節點,另一個用來指向當前節點的前一個節點。遞歸的終止條件是當前節點為null,即已經反轉到鏈表的尾部。
以下是使用遞歸實現單鏈表反轉的Java代碼:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
class LinkedList {
Node head;
LinkedList() {
head = null;
}
// 遞歸反轉鏈表
Node reverse(Node currentNode, Node previousNode) {
// 遞歸終止條件
if (currentNode == null) {
return previousNode;
}
// 保存當前節點的下一個節點
Node nextNode = currentNode.next;
// 將當前節點的next指針指向前一個節點
currentNode.next = previousNode;
// 遞歸反轉剩余部分
return reverse(nextNode, currentNode);
}
// 插入節點到鏈表尾部
void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node currentNode = head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
}
// 打印鏈表
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
System.out.println("原始鏈表:");
list.printList(list.head);
// 反轉鏈表
list.head = list.reverse(list.head, null);
System.out.println("\n反轉后的鏈表:");
list.printList(list.head);
}
}
輸出結果為:
原始鏈表: 1 2 3 4 反轉后的鏈表: 4 3 2 1