单链表反转--递归非递归实现

Java接口: ListNode reverseList(ListNode head)

非递归的实现

有2种,参考

  • 头结点插入法
  • 就地反转

递归的实现

  1. Divide the list in two parts - first node and rest of the linked list.
  2. Call reverse for the rest of the linked list.
  3. Link rest to first.
  4. Fix head pointer

  • Time Complexity: O(n)
  • Space Complexity: O(1)

    Java实现,第4步要稍微变通一下:用一个全局头结点dummy指针来保存新链表的head。 需要一个辅助的函数 void reverseList(ListNode head) (不带返回值的函数)
	ListNode dummy = new ListNode(-1);
public ListNode reverseListRecu(ListNode head) {
if (head == null)
return head;
reverse(head);
return dummy.next;
} private void reverse(ListNode head){
ListNode first = head;
ListNode rest = first.next;
if(rest == null) {
dummy.next = first;
return;
}
reverse(rest);
first.next.next = first;
first.next = null;
}

最新文章

  1. 利用Nginx实现域名转发 不修改主机头
  2. C#批量插入数据到Sqlserver中的三种方式
  3. HITOJ 2662 Pieces Assignment(状压DP)
  4. python 循环
  5. jQuery免费资料
  6. 使用 Media Center 遥控器(Windows Vista Premium)
  7. WPF 设置WebBrowser控件不弹脚本错误提示框
  8. sqlcipher for android
  9. Winform界面中主从表编辑界面的快速处理
  10. deeplearning.ai 神经网络和深度学习 week4 深层神经网络 听课笔记
  11. 易趣:使用MongoDB创建关键业务的多数据中心应用
  12. Codeforces Gym 101190M Mole Tunnels - 费用流
  13. VS2010与Matlab2010b混合编程
  14. 照葫芦画瓢系列之Java --- Maven的集成和使用
  15. linux cp 和scp详解
  16. vagrant up下载box慢的解决办法
  17. EZ 2018 05 01 NOIP2018 模拟赛(十一)
  18. 面试题-----求单链表的倒数第k个节点
  19. c#_导出table功能
  20. noip2018 D1T3 赛道修建

热门文章

  1. 关于学习angularJS 的 心里路程(二)
  2. 可以链接不同源的资源的html元素(能实现跨域)
  3. Where is the Global.asax.cs file
  4. 新一代IDE Light Table开源:让编程工作更简单
  5. 【C#】OOP之继承那点事
  6. <实训|第三天>Linux登录界面的修改以及Richard Stallman、自由软件运动
  7. iOS-MVC详解
  8. XtraReport 实例化 打印
  9. MVC+EF 随笔小计————Html Helpers
  10. (推荐)jquery.pagination.js分页
  11. 错误处理try catch
  12. .net dynamic动态加属性
  13. HTTP请求到爬虫代码的终南捷径
  14. linux内核源码分析 - nvme设备的初始化
  15. CS通用项目系统搭建——三层架构第二天
  16. C#使用反射获取对象变化的情况
  17. Android学习之基础知识九 — 数据存储(持久化技术)之SQLite数据库存储
  18. mysql锁表与不锁表设置主从复制的方法
  19. SaltStack salt-key 命令
  20. SqlServer 获取汉字的拼音首字母