《剑指offer》面试题16 反转链表 Java版

时间:2022-09-13 21:05:27

(输入链表的头节点,反转链表)

书中方法:对于一个链表,我们只能从头往后遍历,如果要反转,我们需要更改当前节点的next域指向前一个节点,此时链表断开,为了能继续修改下一个节点的next域,我们还要维护下一个节点。

	public ListNode reverse(ListNode first){
if(first == null)return first;
ListNode last = null;
ListNode now = first;
ListNode next = first.next;
while(now != null){
now.next = last; last = now;
now = next;
if(now != null){
next = now.next;
}
}
return last;
}

方法二:书后面还提到了递归的方法。自己写的逻辑比较不清楚,在网上找了一个版本。这个方法的思路是:递归返回的是当前节点右侧已经反转好的链表的头节点,对于当前的节点,将它连接到已经reverse好的链表的末尾,返回值是添加了该节点的新链表头。先递归后处理,最后的返回值是反转后的节点,每次递归返回的是添加了当前节点的反转后的链表。注意递归出口的处理。

	public ListNode reverse2(ListNode first){
if(first == null || first.next == null)return first; ListNode newHead = reverse2(first.next);
first.next.next = first;
first.next = null; return newHead; }

《剑指offer》面试题16 反转链表 Java版的更多相关文章

  1. 剑指Offer:面试题16——反转链表(java实现)

    问题描述 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点.链表结点如下: public class ListNode { int val; ListNode next = n ...

  2. 剑指Offer - 九度1518 - 反转链表

    剑指Offer - 九度1518 - 反转链表2013-11-30 03:09 题目描述: 输入一个链表,反转链表后,输出链表的所有元素.(hint : 请务必使用链表) 输入: 输入可能包含多个测试 ...

  3. 剑指Offer面试题:14.链表的倒数第k个节点

    PS:这是一道出境率极高的题目,记得去年参加校园招聘时我看到了3次,但是每次写的都不完善. 一.题目:链表的倒数第k个节点 题目:输入一个链表,输出该链表中倒数第k个结点.为了符合大多数人的习惯,本题 ...

  4. 剑指offer 面试题35.复杂链表的复制

    时间O(N),空间O(N) /* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomList ...

  5. C++版 - 剑指offer 面试题16:反转链表(Leetcode 206: Reverse Linked List) 题解

    面试题16:反转链表 提交网址: http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId= ...

  6. 【剑指offer 面试题16】反转链表

    思路: 用三个指针preNode.curNode.nextNode完成. #include <iostream> using namespace std; struct ListNode ...

  7. 剑指Offer面试题16(Java版):反转链表

    题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点. 解决与链表相关的问题总是有大量的指针操作.而指针操作的代码总是easy出错的. 非常多的面试官喜欢出链表相关的问题,就是 ...

  8. 剑指offer(15)反转链表

    题目描述 输入一个链表,反转链表后,输出链表的所有元素. 题目分析 至少需要三个指针pPre(指向前一个结点).pCurrent(指向当前的结点,在代码中就是pHead).pPnext(指向后一个结点 ...

  9. 剑指offer十五之反转链表

    一.题目 输入一个链表,反转链表后,输出链表的所有元素. 二.思路 详细分析见代码注释 三.代码 public class Solution {     public ListNode Reverse ...

随机推荐

  1. jquery 的 sort 函数

    members = [45, 23, 12, 34];members = members.sort(function(a, b){return a-b; );这里面a-b为升序,b-a降序排列:但a, ...

  2. Redhat常见问题

    1.现象:hadoop用户启动startx时失败,报如下提示 Fatal server error: PAM authentication failed, cannot start X server. ...

  3. Uiviewcontroller 控制器的生命周期

    这是一个ViewController完整的声明周期,其实里面还有好多地方需要我们注意一下: 1:initialize函数并不会每次创建对象都调用,只有在这个类第一次创建对象时才会调用,做一些类的准备工 ...

  4. 11&period;4&period;2 排序或合并文件(sort命令) - 51CTO&period;COM

    11.4.2 排序或合并文件(sort命令) - 51CTO.COM 11.4.2 排序或合并文件(sort命令) 2010-03-12 14:37 陆松年 电子工业出版社 我要评论(0) 字号:T ...

  5. 从0到1学习node&lpar;七&rpar;之express搭建简易论坛

    我们需要搭建的这个简易的论坛主要的功能有:注册.登录.发布主题.回复主题.下面我们来一步步地讲解这个系统是如何实现的. 总索引: http://www.xiabingbao.com/node/2017 ...

  6. 从源码看JDK提供的线程池(ThreadPoolExecutor)

    一丶什么是线程池 (1)博主在听到线程池三个字的时候第一个想法就是数据库连接池,回忆一下,我们在学JavaWeb的时候怎么理解数据库连接池的,数据库创建连接和关闭连接是一个比较耗费资源的事情,对于那些 ...

  7. c&num;一些特殊语法

    1.using 语法 using不仅可以作为导入包,重命名类名.还可以释放资源 using (Pen gridLinePen = new Pen(Color.red)) { e.Graphics.Dr ...

  8. MessengerJS

    跨文档通信解决方案 Since modern browsers have native cross-document communication method(the PostMeessage API ...

  9. 【原创】大数据基础之Kerberos(1)简介、安装、使用

    kerberos5-1.17 官方:https://kerberos.org/ 一 简介 The Kerberos protocol is designed to provide reliable a ...

  10. SQL SERVER 一个SQL语句的执行顺序

    一个SQL 语句的执行顺序 1.From (告诉程序 来自哪张表  如果是表表达式 依旧是如此顺序) 2.Where(条件筛选  谓词筛选 ) 3.Group by(分组) 4.Having(分组   ...