首页java反转单向和双向链表

java反转单向和双向链表

时间: 2025-02-18 11:35:41 浏览: 37

### Java 中单向链表和双向链表反转的实现 #### 单向链表反转对于单向链表而言，其结构较为简单，仅包含指向下一个节点的指针。为了实现单向链表的反转，可以通过迭代的方式逐步调整各节点之间的链接方向。 ```java public class SinglyLinkedList { public static ListNode reverseList(ListNode head) { ListNode prev = null; while (head != null) { ListNode nextNode = head.next; // 记录当前节点的下一节点 head.next = prev; // 将当前节点的next设为prev, 反转指针方向 prev = head; // 移动prev到当前节点位置 head = nextNode; // 继续处理下个节点 } return prev; // 返回新的头结点 } static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } } ``` 此方法的时间复杂度为 O(n)，其中 n 是列表中的元素数量[^1]。 #### 双向链表反转双向链表由于存在前后两个指针，因此在执行反转操作时不仅需要改变 `next` 的指向还需要同步更新 `prev` 指针的方向： ```java public class DoublyLinkedList { public static Node reverse(Node node) { Node temp = null; Node current = node; while (current != null) { temp = current.prev; // 临时保存前驱节点 current.prev = current.next; // 前驱变为后继 current.next = temp; // 后继变为原来的前驱 current = current.prev; // 进入下一个待处理节点 } if(temp != null ) { node = temp.prev; // 更新头部指针至新起点 } return node; } static class Node { int data; Node next, prev; Node(int d) {data = d;} } } ``` 这段代码同样具有 O(n) 时间复杂度，并且通过交换每个节点上的 `next` 和 `prev` 来完成整个过程。

阅读全文