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

思路分析

需要考虑以下因素

数据量是否会很大。

空间是否有限制。

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

时间复杂度是否有限制。

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

方法一、直接递归（简单，但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 {

public void reverse(ListNode head) { if (head == null || head.next == null) { return ; } ListNode currentNode = head; Stack > stack = new Stack<>(); while (currentNode != null) { stack.push(currentNode); ListNode 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 val; public ListNode(T val) { this.val = val; } ListNode next;}

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/50810.html