java双链表递归反转

### Java中通过递归方式实现双链表的反转 在Java中，双链表是一种具有前后指针的数据结构。为了通过递归的方式实现双链表的反转，可以基于单链表反转的思想进行扩展。以下是具体的实现逻辑： #### 实现思路 1. **终止条件**：当当前节点为空或者其下一个节点为空时，返回该节点作为新的头节点。 2. **递归调用**：对于每个节点 `current`，将其后续部分视为一个新的子链表并递归处理。 3. **调整指针方向**： - 将 `current.next.prev` 指向 `current` 的前驱位置。 - 更新 `current.prev` 和 `current.next` 的指向关系。 4. **返回新头节点**。 下面是完整的代码实现： ```java class DoublyLinkedList { static class Node { int data; Node prev, next; public Node(int data) { this.data = data; this.prev = null; this.next = null; } } private Node head; // 添加节点到链表尾部的方法（用于测试） public void append(int data) { if (head == null) { head = new Node(data); return; } Node current = head; while (current.next != null) { current = current.next; } Node newNode = new Node(data); current.next = newNode; newNode.prev = current; } // 打印链表正序遍历的结果 public void printForward() { Node temp = head; System.out.print("Head -> "); while (temp != null) { System.out.print(temp.data + " <-> "); temp = temp.next; } System.out.println("null"); } // 打印链表逆序遍历的结果 public void printBackward() { Node temp = getTail(); System.out.print("null <- "); while (temp != null) { System.out.print(temp.data + " <- "); temp = temp.prev; } System.out.println("Head"); } // 获取尾节点 private Node getTail() { Node temp = head; while (temp != null && temp.next != null) { temp = temp.next; } return temp; } // 递归反转双链表的核心方法 public Node reverseList(Node node) { if (node == null || node.next == null) { return node; // 新的头部节点 } // 递归反转剩余的部分 Node rest = reverseList(node.next); // 调整当前节点与其下一节点之间的双向连接 node.next.next = node; node.prev = node.next; node.next = null; return rest; // 返回新的头部节点 } // 外部接口：反转整个链表 public void reverse() { if (head != null) { head = reverseList(head); } } } ``` #### 测试代码 以下是一个简单的测试程序来验证上述实现的功能： ```java public class Main { public static void main(String[] args) { DoublyLinkedList list = new DoublyLinkedList(); // 构建初始链表 for (int i = 1; i <= 5; i++) { list.append(i); } System.out.println("Original List:"); list.printForward(); // 正序打印原始链表 list.printBackward(); // 倒序打印原始链表 // 反转链表 list.reverse(); System.out.println("\nReversed List:"); list.printForward(); // 正序打印反转后的链表 list.printBackward(); // 倒序打印反转后的链表 } } ``` 运行结果可能如下所示： ``` Original List: Head -> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> null null <- 5 <- 4 <- 3 <- 2 <- 1 <- Head Reversed List: Head -> 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> null null <- 1 <- 2 <- 3 <- 4 <- 5 <- Head ``` #### 关键点说明 - 在递归过程中，每次都将当前节点的 `next` 设置为其原来的 `prev`，并将 `prev` 设置为原来 `next` 的值[^1]。 - 当到达链表末端时，最后一个非空节点成为新的头节点，并逐层回溯完成其余节点的反转操作[^3]。 ---