单向链表逆序（如何实现一个高效的单向链表逆序输出）

科技前沿 • 2025-05-01 07:59 • 阅读 40

大家好，我是讯享网，很高兴认识大家。

思路分析

需要考虑以下因素

数据量是否会很大。

空间是否有限制。

原始链表的结构是否可以更改。

时间复杂度是否有限制。

讯享网

一个链表节点需要输出的元素有多个，例如链表中存的是自定义对象，有多个字段。

方法一、直接递归（简单，但O(n)空间复杂度不支持大数据量）

// 直接递归实现核心代码片段public void reverse(head){ // 递归终止条件 if(head.next == null){ print(head); return; } // 下一层需要做的事儿 reverse(head.next); // 本层需要做的事儿 print(head);

方法二、采用栈进行存储（O(n)时间复杂度，但不支持大数据量，栈中需要存储所有节点）

// 采用栈进行存储实现核心代码片段public void reverse(head){ Node cur = head; // 将所有元素入栈 while(cur != null){ stack.push(cur); cur = cur.next; } // 将所有元素出栈 while(!stack.isEmpty){ print(stack.poll); }}

方法三、直接遍历（不需要额外存储空间，但O（n^2）时间复杂度）

// 直接遍历实现核心代码public void reverse(head){ Node cur = head; int count = 0; // 统计链表节点个数 while(cur != null){ count ++; cur = cur.next; } // 每次从前往后进行扫描输出 for(int i = count; i > 0; i–){ int tmp = i; cur = head; while(tmp– != 0){ cur = cur.next; } print(cur) }}

方法四、翻转链表再遍历（O(n)时间复杂度且不需要额外存储空间，但需要改变原始链表结构）

// 翻转链表实现核心代码public void reverse(head){ Node cur = head.next; Node pre = head; pre.next = null; Node tmp = new Node(); // 翻转链表 while(cur != null){ tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } // 输出 while(pre != null){ print(pre); pre = pre.next; } }

方法五、头插法新建空链表（简单，但是O(n)空间复杂度）

// 头插法新建空链表实现核心代码public void reverse(head){ Node result = copy(head); Node cur = head; cur = cur.next; // 新建链表节点，头插法构建 while(cur != null){ Node tmp = copy(cur.next); tmp.next = pre; pre = tmp; cur = cur.next; }}

下面给一个完成的代码写法，供各位参考

class Solution<T> { public void reverse(ListNode<T> head) { if (head == null || head.next == null) { return ; } ListNode<T> currentNode = head; Stack<ListNode<T>> stack = new Stack<>(); while (currentNode != null) { stack.push(currentNode); ListNode<T> tempNode = currentNode.next; currentNode.next = null; // 断开连接 currentNode = tempNode; } head = stack.pop(); currentNode = head; while (!stack.isEmpty()) { currentNode.next = stack.pop(); currentNode = currentNode.next; } }} class ListNode<T>{ T val; public ListNode(T val) { this.val = val; } ListNode<T> next;}

单向链表逆序（如何实现一个高效的单向链表逆序输出）

相关推荐