精华内容
下载资源
问答
  • 面试的时候经常会出现的问题,现在都做一遍,回忆一下...需要一个tmp指针,临时保存p->next的地址,这个在改变一个节点的next地址时,经常会用到示意图代码实现#includestruct ListNode{int data;ListNode *next;}Li...

    面试的时候经常会出现的问题,现在都做一遍,回忆一下,练练手.

    这个题目需要注意两点:

    1.head->next 要先设置为NULL ,否则反转后,它还是指向之前的next节点

    2.需要有一个tmp指针,临时保存p->next的地址,这个在改变一个节点的next地址时,经常会用到

    示意图

    L3Byb3h5L2h0dHBzL3d3dy5jbmJsb2dzLmNvbS9zbmFrZS1oYW5kL2FkbWluLw==.jpg

    0f328ebb8044edb1ce1ef3fb779d454f.png

    代码实现

    #include

    struct ListNode{

    int data;

    ListNode *next;

    }

    ListNode* reverse(ListNode* head){

    ListNode *p,*tmp ;

    p = head->next;

    head->next=NULL;

    while(p){

    tmp = p->next; //图1 保存p->next

    p->next = head; //图1 反向指向head

    head = p ; //图2 head 指向p

    p = tmp; //图2 p指向p->next

    }

    return head;

    }

    [LeetCode] 链表反转相关题目

    暂时接触到LeetCode上与链表反转相关的题目一共有3道,在这篇博文里面总结一下.首先要讲一下我一开始思考的误区:链表的反转,不是改变节点的位置,而是改变每一个节点next指针的指向. 下面直接看看 ...

    链表回文判断(基于链表反转)—Java实现

    学习数据结构的时候遇到一个经典的回文链表问题 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构. 如果有链表反转的基础,实现链表回文判断就简单的多,如 ...

    经典算法(三) 单链表 反转 & 是否相交/成环 & 求交点 等

    参考文章: 判断链表是否相交:http://treemanfm.iteye.com/blog/2044196 一.单链表反转 链表节点 public class Node { private int ...

    链表反转leetcode206

    最近准备结束自己的科研生涯,准备要开始找工作了,准备在LEETCODE刷刷题...刷的前40题全部用python刷的,各种调包速度奇快,后被师哥告知这样没意义,于是准备开始回归C++,Python用的 ...

    链表反转 (Multi-method)

    链表反转是链表相关问题最基础的知识,做完LeetCode中LinkedList后才会有这种体会,因为ACM算法中不会涉及这一部分.解决这一问题有多种方法,在面试中面试官通常也会要求写出多种.包括sta ...

    java实现单链表反转

    一.简介 经查阅,主要有两种方法实现链表反转,递归反转法和遍历反转法: 递归: 在反转当前结点之前先反转其后边的结点,即.从尾结点开始逆向反转各个节点的指针域指向: 遍历:从前往后反转各个结点的指针域 ...

    C++ 单向链表反转

    单向链表反转,一道常见的面试题,动手实现下. #include "stdafx.h" #include struct Node{ int data ...

    c语言:链表排序, 链表反转

    下面将实现链表排序的排序和遍历显示功能: 所定义的链表结构如下: head -> p1 -> p2 ->p3 ->....->pn; head的本身不作为数据节点,hea ...

    【Java数据结构】Java数据结构之链表反转

    我们都知道用C可以很简单的实现单链表反转,今天来学习下,在Java中如何实现链表反转. 思路很简单,定义一个类,这个类分成2块,一块是表示自身的标志,另外一个存储指向下一个元素的引用.通过互换相邻两个 ...

    随机推荐

    Linux kill -9 和 kill -15 的区别

    “我的天呀!”,网页编辑没有自动保存草稿的功能.害的我昨天写的东西都没有了.算了,不计较这些了.反正也没写多少. 嘻嘻. 大家对kill -9 肯定非常熟悉,在工作中也经常用到.特别是你去重启tomc ...

    java 显示目录下全部文件

    package gao.org; import java.awt.HeadlessException; import java.io.File; import javax.swing.JFileCho ...

    [转载] java多线程学习-java.util.concurrent详解(四) BlockingQueue

    转载自http://janeky.iteye.com/blog/770671 ------------------------------------------------------------- ...

    福州大学软件工程1916|W班 第2次作业成绩排名

    作业链接: 结对第一次-原型设计(文献摘要热词统计) 评分准则: 本次作业评分分为两部分,一部分是博客分数(满分25分),另一部分是工程能力分数(满分30分). 博客分数评分标准: 1.在随笔开头请加 ...

    rapidjson 的练习

    // JsonCpp.cpp: 定义控制台应用程序的入口点. // #include "stdafx.h" #include #include &lt ...

    luogu P1439 【模板】最长公共子序列(LCS)

    题目qwq (第一道蓝题) 先把第一个序列每个数出现的顺序记下来(数字本身不用记), 然后第二个序列的每个数都对照它的顺序,这样只要得到一个升序的序列就行了qwq 如果遇到出现顺序在前面的数,就用二分 ...

    ActiveMQ安装与入门程序 & JMS的消息结构

    1.Activemq安装 直接到官网下载:记住apache的官网是域名反过来,比如我们找activemq就是activemq.apache.org. 最新版本要求最低的JDK是8,所以最好在电脑装多个 ...

    在IDEA中实战Git

    工作中多人使用版本控制软件协作开发,常见的应用场景归纳如下: 假设小组中有两个人,组长小张,组员小袁 场景一:小张创建项目并提交到远程Git仓库 场景二:小袁从远程git仓库上获取项目源码 场景三:小 ...

    CouldnotcreatetheJavaVirtualMachine/1709

    Section A: symptom --------------------   SWPM1024 S/4hana 1709 安装过程中遇到error, 错误提示错误信息在/tmp/sapinst_ ...

    展开全文
  • 题目描述:  一个单向链表,链表当中可能出现“”。如何用程序判断出这个链表是环链表? ...【1】【算法】如何判断链表有环 地址:https://blog.csdn.net/u010983881/article/detai...

    题目描述: 

    有一个单向链表,链表当中有可能出现“环”。如何用程序判断出这个链表是有环链表?

    • 不允许修改链表结构。
    • 时间复杂度O(n),空间复杂度O(1)。

    解法:

    (1) 穷举遍历

    (2)哈希表缓存

    (3)快慢指针

     

    Reference:

    【1】【算法】如何判断链表有环

    地址:https://blog.csdn.net/u010983881/article/details/78896293

    展开全文
  • 如何判断链表有环

    千次阅读 2019-03-11 10:26:57
    如何判断单链表是否存在 一个单向链表链表当中可能出现“”,就像题图这样。... 时间复杂度O(n),空间复杂度O(1)。 方法一、穷举遍历 方法一:首先从头节点开始,依次遍历单链表的每...

    转自:https://blog.csdn.net/u010983881/article/details/78896293

    如何判断单链表是否存在环

    有一个单向链表,链表当中有可能出现“环”,就像题图这样。如何用程序判断出这个链表是有环链表?

    • 不允许修改链表结构。
    • 时间复杂度O(n),空间复杂度O(1)。

    方法一、穷举遍历

    方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的节点,就继续遍历下一个新节点,继续重复刚才的操作。

    例如这样的链表:A->B->C->D->B->C->D, 当遍历到节点D的时候,我们需要比较的是之前的节点A、B、C,不存在相同节点。这时候要遍历的下一个新节点是B,B之前的节点A、B、C、D中恰好也存在B,因此B出现了两次,判断出链表有环。

    假设从链表头节点到入环点的距离是D,链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 , 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间,空间复杂度可以简单地理解成为O(1)。

    方法二、哈希表缓存

    **首先创建一个以节点ID为键的HashSet集合,用来存储曾经遍历过的节点。然后同样是从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就用新节点和HashSet集合当中存储的节点作比较,如果发现HashSet当中存在相同节点ID,则说明链表有环,如果HashSet当中不存在相同的节点ID,就把这个新节点ID存入HashSet,之后进入下一节点,继续重复刚才的操作。

    这个方法在流程上和方法一类似,本质的区别是使用了HashSet作为额外的缓存。

    假设从链表头节点到入环点的距离是D,链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S,可以简单理解为O(N)。而算法的空间复杂度还是D+S-1,可以简单地理解成O(N)。

    方法三、快慢指针

    首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

    例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,指针1移动到了节点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指针2移动到了节点B。第三轮循环,指针1移动到了节点D,指针2移动到了节点D,此时两指针指向同一节点,判断出链表有环。

    此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身后再次追上并超过,原因很简单,因为跑道是环形的。

    /**
     * 判断单链表是否存在环
     * @param head
     * @return
     */
    public static <T> boolean isLoopList(ListNode<T> head){
        ListNode<T> slowPointer, fastPointer;
    
        //使用快慢指针,慢指针每次向前一步,快指针每次两步
        slowPointer = fastPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
    
            //两指针相遇则有环
            if(slowPointer == fastPointer){
                return true;
            }
        }
        return false;
    }
     
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    假设从链表头节点到入环点的距离是D,链表的环长是S。那么循环会进行S次(为什么是S次,有心的同学可以自己揣摩下),可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所以空间复杂度是O(1)。

    如何找出有环链表的入环点?

    根据这篇文章:链表中环形的入口,我们来分析一下入环口和我们上面这个快慢指针相遇点的关系。

    当fast若与slow相遇时,slow肯定没有走遍历完链表(不是一整个环,有开头部分,如上图)或者恰好遍历一圈(未做验证,看我的表格例子,在1处相遇)。于是我们从链表头、相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点(慢指针走了n步,第一次相遇在c点,对慢指针来说n=s+p,也就是说如果慢指针从c点再走n步,又会到c点,那么顺时针的CB距离是n-p=s,但是我们不知道s是几,那么当快指针此时在A点一步一步走,当快慢指针相遇时,相遇点恰好是圆环七点B(AB=CB=s))。

    /**
     * 找到有环链表的入口
     * @param head
     * @return
     */
    public static <T> ListNode<T> findEntranceInLoopList(ListNode<T> head){
        ListNode<T> slowPointer, fastPointer;
    
        //使用快慢指针,慢指针每次向前一步,快指针每次两步
        boolean isLoop = false;
        slowPointer = fastPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
    
            //两指针相遇则有环
            if(slowPointer == fastPointer){
                isLoop = true;
                break;
            }
        }
    
        //一个指针从链表头开始,一个从相遇点开始,每次一步,再次相遇的点即是入口节点
        if(isLoop){
            slowPointer = head;
            while(fastPointer != null && fastPointer.next != null){
                //两指针相遇的点即是入口节点
                if(slowPointer == fastPointer){
                    return slowPointer;
                }
    
                slowPointer = slowPointer.next;
                fastPointer = fastPointer.next;
            }
        }
        return null;
    }
     
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    如何判断两个单链表是否相交,以及相交点

    方法一、直接法

    直接判断第一个链表的每个结点是否在第二个链表中,时间复杂度为O(len1*len2),耗时很大

    方法二、利用计数

    如果两个链表相交,则两个链表就会有共同的结点;而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点,就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序,建立hash表,然后针对第二个链表的每个节点的地址查询hash表,如果它在hash表中出现,则说明两个链表有共 同的结点。这个方法的时间复杂度为:O(max(len1+len2);但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度,增加 了存储空间。

    以链表节点地址为值,遍历第一个链表,使用Hash保存所有节点地址值,结束条件为到最后一个节点(无环)或Hash中该地址值已经存在(有环)。

    再遍历第二个链表,判断节点地址值是否已经存在于上面创建的Hash表中。
    这个方面可以解决题目中的所有情况,时间复杂度为O(m+n),m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型,假设链表都是在堆中动态创建的,可以使用堆的起始地址作为偏移量,以地址减去这个偏移量作为Hash函数

    方法三、利用有环链表思路

    对于两个没有环的链表相交于一节点,则在这个节点之后的所有结点都是两个链表所共有的。如果它们相交,则最后一个结点一定是共有的,则只需要判断最后一个结点是否相同即可。时间复杂度为O(len1+len2)。对于相交的第一个结点,则可求出两个链表的长度,然后用长的减去短的得到一个差值 K,然后让长的链表先遍历K个结点,然后两个链表再开始比较。

    还可以这样:其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个

    参考资料

    展开全文
  • 如何判断链表有环? 1,什么是环链表? 一个有环的链表 :eg. A->B->C->D->B->C->D 如图: 2,如何判断链表有环? 第一种方法:遍历:出现两个相同节点则证明出现,利用HashSet存放已遍历...

    如何判断链表有环?

    1,什么是有环链表?

    • 一个有环的链表 :eg. A->B->C->D->B->C->D
    • 如图:
      在这里插入图片描述

    2,如何判断链表有环?

    • 第一种方法:遍历:出现两个相同节点则证明出现环,利用HashSet存放已遍历的节点,如果发现已经有节点存在于HashSet中,则证明有环出现。
      优点:简单
      缺点:时间复杂度高O(n),空间复杂度O(n)

    代码实现:

    //构造节点内部类
        
     /**
         * 遍历:出现两个相同节点则证明出现环
         *
         * @param head 头
         */
        private void method1(Node head) {
            Set<String> data = new HashSet<>();
            while (head.next != null) {
                data.add(head.data);
                head = head.next;
                if (data.contains(head.data)) {
                    System.out.println("出现环!");
                    break;
                }
            }
        }
    
    
    • 第二种方法:首先创建两个指针P1和P2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环,这样移动两个指针,如果存在环,总会有P1和P2相遇的时候。
      代码:
        
    
     /**
         * 两个指针判断
         * 例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,
         * 指针1移动到了节点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指
         * 针2移动到了节点B。第三轮循环,指针1移动到了节点D,指针2移动到了节点D,
         * 此时两指针指向同一节点,判断出链表有环
         *
         * @param head 头
         */
        private static void method2(Node head) {
            Node p1, p2;
            p1 = head;
            p2 = head.next;
            while (!p1.data.equals(p2.data)) {
                if (p2.next == null || p2.next.next == null) {
                    System.out.println("无环,结束!");
                    return;
                }
                p1 = p1.next;
                p2 = p2.next.next;
    
            }
            System.out.println("有环!");
        }
    
    
    
    
    • 代码测试
    @Data
        static class Node {
            private Node next;
            private String data;
        }
    
    
        @Test
        public void test01() {
    
            //构造一个循环链表 A->B->C->D->B->C->B
    
            Node A = new Node();
            A.data = "A";
    
            A.next = new Node();
            Node B = A.next;
            B.data = "B";
    
            B.next = new Node();
            Node C = B.next;
            C.data = "C";
    
            C.next = new Node();
            Node D = C.next;
            D.data = "D";
    
            //环连接
            D.next = B;
    
            method1(A);
            method2(A);
        }
    
    
    
    

    测试结果:
    在这里插入图片描述

    展开全文
  • 如何判断链表有环

    2020-05-19 21:39:45
    一个单向链表,链表中可能出现 “”,就像下图这样。...如果相同,则判断链表有环,如果不同,则继续下一循环。 假设链表的节点数量是n,则该算法的时间复杂度是O(n)。除两个结点外,没有使用任何.
  • 经典面试题 如何判断链表有环 参考链接 http://blog.csdn.net/thefutureisour/article/details/8174313 http://blog.csdn.net/liuxialong/article/details/6555850 题目背景 给定一个单链表,只给出头指针\(h\),...
  • 判断链表有环&求循环列表长&求循环列表入点 关于更多的链表实现可以从下方直通车达到: 单向链表 双向链表 循环链表 本篇希望着重介绍的是结合数学中的追及问题与循环列表来达到判断列表有环和求长 ...
  • 时间复杂度O(n),空间复杂度O(1)。方法一、穷举遍历方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作...
  • 如何判断链表有环(三种方法)

    千次阅读 2019-06-02 09:16:15
    方法一、穷举遍历 ...点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的 节点,就继续遍历下一个新节点,继续重复刚才的操作。 例如这样的链表:A->B->...
  • @牛客网刷题:利用空间复杂度O(1),判断链表是否有环 解题思路:快慢指针,一个指针走一步,另一个指针走两步,如果没有,则快指针肯定先到指针末尾,如果有环,则总一天快指针追上慢指针; /** * Definition ...
  • 算法 链表有环
  • 判断链表是否有环

    2021-04-24 14:52:54
    判断链表是否有环 题目描述 判断给定的链表中是否有环。如果有环则返回true,否则返回false。要求空间复杂度为O(1)。 其中,结点的定义如下: class ListNode: def __init__(self, x): self.val = x self.next = ...
  • 一个单向链表,链表中可能出现,如何判断链表是否有环? 二、解题思路 方法一: 首先从头节点开始,依次遍历单链表中的每一个节点。每遍历一个新节点,就从头检查新节点之前的所有结点,用新节点和此结点之前...
  • 判断链表是否有环。  2. 如果链表有环,请找出入口。  3. 计算的大小。 思路:快慢指针  分别定义一个快指针fast和慢指针slow,快指针一次走两步,慢指针一次走一步。如果链表没有,那么fast最终会...
  • 1、怎么判断一个单链表是否带  如果单链表带,那么从链表头开始时遍历就会进入死循环。可以用两个速度不同的指针,先让两个指针...// 判断链表是否带,若带给出相遇点 PNode HasCircle(PNode pHead) { PNo
  • 判断链表是否有环是一个经典的用双指针来解决的问题。 一个慢指针一次走一步,一个快指针一次走两步, 如果有环的话,它们最终会在内相遇;如果没有的话,最终快指针会先到达链表的尾部。 复杂度: 时间复杂度:...
  • 判断给定的链表中是否有环。如果有环则返回true,否则返回false。 你能给出空间复杂度的解法么? 输入 无 输出 无 思路: 快慢指针判断法:设置两个指针,从同一个起点出发,一个速度为2个节点/次,一个速度为1个...
  • 问题一:判断链表是否有环及入结点问题 1、先判断是否有环 设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在,则fast必定先进入,而slow后进入,两个指针...
  • 如何判断链表有环1、题目分析方法一方法二方法三【双指针】2、代码实现 1、题目分析 一个单向链表,链表中可能出现“”,就像下图这样。如何用程序来判断该链表是否为环链表呢? 方法一 方法流程: 从头...
  • 分析:(当前链表中的数据无重复) ...2.借助额外空间,建立一个HashSet,将已经遍历过的节点的值放入集合中,若遍历至当前节点时,集合中已经存在该节点的值,则说明链表有环时间复杂度为O(N),额外的空间...
  •   给定一个链表,判断链表中是否有环。   为了表示给定链表中的,我们使用证书pos来表示链表连接到链表中的位置(索引从0开始),如果pos是-1,则在该链表中没有。   示例: 输入:head = [3,2,0,-4],...
  • 一个单向链表,链中可能”,如何用程序判断呢? 方法1(最低效) 最常想到的是:首先从头结点开始遍历整个链表,每遍历一个,就和之前遍历过的比较,,, 这相当于每次遍历了两遍,无疑是扩大了链表“ 遍历 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,590
精华内容 7,036
关键字:

判断链表有环时间复杂度