文档章节

剑指Offer(Java版):反转链表

一贱书生
 一贱书生
发布于 2016/07/20 19:30
字数 842
阅读 10
收藏 0

题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

解决与链表相关的问题总是有大量的指针操作,而指针操作的代码总是容 易出错的。很多的面试官喜欢出链表相关的问题,就是想通过指针操作来考察应聘者的编码功底。为了避免出错,我们最好先进行全面的分析。在实际软件开发周期 中,设计的时间通常不会比编码的时间短。在面试的时候我们不要急于动手写代码,而是一开始仔细分析和涉及,这将会给面试官留下好的印象。与其给出一段漏洞 百出的代码,倒不如仔细分析再写出鲁棒性好的代码。

为了正确的反转一个链表,需要调整链表中指针的方向。为了将调整指针 这个复杂的过程分析清楚,我们可以借助图形来直观的分析。在图中所示的链表中,h,i,j是3个相邻的结点。假设经过若干的操作,我们已经把结点h之前的 指针调整完毕,这些结点的m_pNext都指向前面的一个结点。接下来我们把i的m_pNext指向h,此时的链表结构如图b所示。

不难注意到,由于结点i的m_pNext指向了它的前一个结点,导致我们无法在链表中遍历到结点j。为了避免链表在结点i处断开,我们需要在调整结点i的m_pNext之前,把结点j保存下来。

也就是说我们在调整结点i的m_pNext指针时,除了需要知道结点 i本身之外,还需要i的前一个结点h,因为我们需要把结点i的m_pNext指向结点h,同时,我们还实现需要保存i个结点j,以防止链表断开。因此相应 地我们需要三个指针,分别指向当前遍历到的结点,它的前一个结点和后一个结点。

最后我们试着找到反转链表的头结点。不难分析出反转后的链表的头结点是原始链表的尾节点。什么结点是尾节点,自然是m_pNext为 Null 的结点。

分析写出下面的代码:

package cglib;
class ListNode
{
   int data;
   ListNode nextNode;
}

public class DeleteNode {
    public static void main(String[] args) {
        ListNode head=new ListNode();
        ListNode second=new ListNode();
        ListNode third=new ListNode();
        ListNode forth=new ListNode();
        head.nextNode=second;
        second.nextNode=third;
        third.nextNode=forth;
        head.data=1;
        second.data=2;
        third.data=3;
        forth.data=4;
        DeleteNode test=new DeleteNode();
        ListNode resultListNode=test.reverseList(head);
        System.out.println(resultListNode.data);
        }
    public ListNode reverseList(ListNode head){
        if(head == null)  
            return null;  
        ListNode preListNode = null;  
        ListNode nowListNode = head;  
          
        while(nowListNode != null){ //1->2->3->4
            ListNode nextListNode = nowListNode.nextNode;   //保存下一个结点2  
            nowListNode.nextNode = preListNode;  //当前结点指向前一个结点null<-1
            preListNode = nowListNode;                  //前任结点 等于现任节点 null<-1<-2
            nowListNode = nextListNode;                 //现任节点等于下一结点  null<-1<-2,然后从2开始循环,直至preListNode=4,nowListNode=null
        }  
        return preListNode;  
        }
}


输出 4

 

拓展: 递归实现同样的反转链表的功能。

public ListNode reverseList(ListNode head){
        if(head==null || head.nextNode==null)  
            return head;  
        else  
        {  //1->2->3->4
            
            ListNode nextNode = head.nextNode; //2
            head.nextNode = null; //null<-1
            ListNode reverseRest = reverseList(nextNode); //从2开始递归
            nextNode.nextNode = head;  //3<-4
            return reverseRest;  
        }  
    }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
面试:用 Java 实现一个 Singleton 模式

面试系列更新后,终于迎来了我们的第一期,我们也将贴近《剑指 Offer》的题目给大家带来 Java 的讲解,个人bogo还是非常推荐《剑指 Offer》作为面试必刷的书籍的,这不,再一次把这本书分享给...

nanchen2251
2018/07/03
0
0
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
01/19
0
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
2018/07/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

AWS自动部署工具codedeploy的部署概述

1)在AWS lambda平台上部署: 三大部分:要部署的内容 --> 部署的配置 --> 更新的lambda函数版本 部署的流程:上传修订的应用程序-->创建一个应用程序-->指定部署组-->指定部署的配置-->指定...

守护-创造
34分钟前
2
0
好程序员教程分享Javascript设计模式

好程序员教程分享Javascript设计模式 方法一 对象字面量表示法   在对象字面量表示法中,一个对象被描述为一组包含在大括号中,以逗号分隔的 name/value 对。对象内的名称可以是字符串或标...

好程序员IT
40分钟前
3
0
fail-fast和fail-safe的介绍和区别

fail-fast和fail-safe 前言 前段时间公司招的实习生在使用迭代器遍历的时候,对集合内容进行了修改,从而抛出ConcurrentModificationException. 然后给他讲解之余也整理了这一篇文章. fail-fa...

群星纪元
42分钟前
3
0
控制反转 IOC

控制反转(Inversion of Control,缩写为IoC)面向对象设计原则,降低代码耦合度 依赖注入(Dependency Injection,简称DI) 依赖查找(Dependency Lookup):容器提供回调接口和上下文条件给...

SibylY
53分钟前
2
0
网络介绍:Kubernetes设计文档

模型和动机 Kubernetes从Docker默认的网络模型中独立出来形成一套自己的网络模型。该网络模型的目标是:每一个pod都拥有一个扁平化共享网络命名空间的IP,通过该IP,pod就能够跨网络与其它物...

xiangyunyan
55分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部