精华内容
下载资源
问答
  • 判断链表有环时间复杂度
    千次阅读
    2019-06-02 09:16:15

    方法一、穷举遍历

    方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历
    新节点之前的所有节点,用新节点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,此时两指针指向同一节点,判断出链表有环。
    
    此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运
    动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身
    后再次追上并超过,原因很简单,因为跑道是环形的。
    假设从链表头节点到入环点的距离是D,链表的环长是S。那么循环会进行S次(为什么是S次,有心的
    同学可以自己揣摩下),可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所
    以空间复杂度是O(1)。
    

    方法四、Set集合大小变化

    评论中有 @长沙小辣椒 同学指出:还可以用 set 遍历链表,把节点放入set里,每次访问下个节点时,
    如果set长度不变,则跳出,说明有环。否则set长度+1,继续遍历。
    该方法时间复杂度是O(N),空间复杂度上因为需要额外等数量的存储空间,所以空间复杂度是O(n)。
    

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

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

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

    方法一、直接法

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

    方法二、利用计数

    如果两个链表相交,则两个链表就会有共同的结点;而结点地址又是结点唯一标识。因而判断
    两个链表中是否存在地址一致的节点,就可以知道是否相交了。可以对第一 个链表的节点地址
    进行hash排序,建立hash表,然后针对第二个链表的每个节点的地址查询hash表,如果它在ha
    sh表中出现,则说明两个链表有共 同的结点。这个方法的时间复杂度为:O(max(len1+len2);
    但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度,增加 了存储空间。
    以链表节点地址为值,遍历第一个链表,使用Hash保存所有节点地址值,结束条件为到最后一个
    节点(无环)或Hash中该地址值已经存在(有环)。再遍历第二个链表,判断节点地址值是否已
    经存在于上面创建的Hash表中。这个方面可以解决题目中的所有情况,时间复杂度为O(m+n),m
    和n分别是两个链表中节点数量。由于节点地址指针就是一个整型,假设链表都是在堆中动态创建
    的,可以使用堆的起始地址作为偏移量,以地址减去这个偏移量作为Hash函数
    

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

    对于两个没有环的链表相交于一节点,则在这个节点之后的所有结点都是两个链表所共有的。如果它
    们相交,则最后一个结点一定是共有的,则只需要判断最后一个结点是否相同即可。时间复杂度为O(
    len1+len2)。对于相交的第一个结点,则可求出两个链表的长度,然后用长的减去短的得到一个差值 
    K,然后让长的链表先遍历K个结点,然后两个链表再开始比较。还可以这样:其中一个链表首尾相连,
    检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个。
    
    更多相关内容
  • 判断链表是否有环

    2021-06-15 18:31:42
    判断链表是否有环的解法很多,下面归纳几种常见算法。 判断链表是否存在 方法一:通过双循环遍历完成,外层循环从头结点开始遍历,对于遍历到一个新节点newNode,内层循环都要从头结点遍历到该新节点的上一个...

    判断链表是否有环的解法有很多,下面归纳几种常见算法。 

    判断链表是否存在环

    方法一:通过双循环遍历完成,外层循环从头结点开始遍历,对于遍历到一个新节点newNode,内层循环都要从头结点遍历到该新节点的上一个节点head。如果链表无环,则newNode和head永不相等,否则就会相等。时间复杂度为O(n^2)。

    public class LinkListCycle {
        public static class Node {
            private int data;
            private Node next;
    
            public Node(int data) {
                this.data = data;
            }
        }
    
        public static void main(String[] args) {
            Node node1 = new Node(5);
            Node node2 = new Node(3);
            Node node3 = new Node(7);
            Node node4 = new Node(2);
            Node node5 = new Node(6);
            Node node6 = new Node(8);
            Node node7 = new Node(1);
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;
            node5.next = node6;
            node6.next = node7;
            node7.next = node7;
            LinkListCycle linkListCycle = new LinkListCycle();
            linkListCycle.hasCycleForMethodOne(node1);
            System.out.println(linkListCycle.getCycleLength(node1));
        }
    
        //判断是否存在环,双重遍历,时间复杂度为O(n^2)
        public boolean hasCycleForMethodOne(Node node) {
            //外部遍历新节点
            Node newNode = node;
            while (newNode != null) {
                //从头节点遍历到新节点的上一个节点
                Node head = node;
                while (head != null && head.next != newNode) {
                    if (head == newNode) {
                        return true;
                    }
    
                    head = head.next;
                }
    
                newNode = newNode.next;
            }
    
            return false;
        }
    }

    方法二:使用HashMap(或者HashSet),以Node节点作为key,遍历链表,如果node节点不存在则添加到集合中,如果节点存在则说明有环。时间复杂度为O(n),空间复杂度为O(n)。

        //使用map查找环,时间复杂度为O(n),空间复杂度为O(n)
        public boolean hasCycleForMethodTwo(Node node) {
            Map<Node, Integer> map = new HashMap<>();
            while (node != null) {
                if (!map.containsKey(node)) {
                    map.put(node, 1);
                } else {
                    //此时的node即为环的入口
                    System.out.println(node);
                    return true;
                }
                node = node.next;
            }
            return false;
        }

    方法三:快慢指针。类似于数学中的追及问题,设置一个快指针,步长为2,设置一个慢指针,步长为1。如果不存在环,则快慢指针不会相遇。如果存在环,则快慢指针会相遇。时间复杂度为O(n),空间复杂度为O(1)。此为最优方法

        //使用快慢指针查找环,时间复杂度为O(n),空间复杂度为O(1)
        public boolean hasCycleForMethodThree(Node node) {
            //快指针,每次走2步
            Node fast = node;
            //慢指针,每次走1步
            Node low = node;
    
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                low = low.next;
    
                //快慢指针相遇,存在环
                if (fast == low) {
                    return true;
                }
            }
            return false;
        }

    求环的长度

    方法一:使用HashMap,对环进行多次遍历。

        //查找环的长度
        public int getCycleLength(Node node) {
            Map<Node, Integer> map = new HashMap<>();
            int count = 0;
            while (node != null) {
                if (!map.containsKey(node)) {
                    map.put(node, 1);
                } else {
                    map.put(node, map.get(node) + 1);
                }
                //对环进行第二遍遍历
                if (map.get(node) == 2) {
                    count++;
                }
    
                //对环第三遍遍历
                if (map.get(node) == 3) {
                    break;
                }
                node = node.next;
            }
            return count;
        }

    方法二:以指针第一次相遇为起点,记录第二次相遇时的步数即为环的长度。

        public int getCycleLength(Node node) {
            //快指针,每次走2步
            Node fast = node;
            //满指针,每次走1步
            Node low = node;
    
            //指针是否相遇
            boolean first = false;
            //环的长度
            int count = 0;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                low = low.next;
    
                if (first) {
                    count++;
                }
    
                //快慢指针相遇,存在环
                if (fast == low) {
                    if (first) {
                        //第二次相遇
                        return count;
                    } else {
                        //第一次相遇
                        first = true;
                    }
                }
            }
            return -1;
        }

    求环的入口

    方法一:见判断链表是否存在环#方法二。

    方法二:设D为从头节点到入环点的步长,逆时针方向,s1为入环点到首次相遇点的步长,s2为从首次相遇点到入环点的步长。在相遇点快慢指针走过的距离为:

    2(D+S1 ) = D+S1 +n(S1 +S2 )-->D = (n-1)(S1 +S2 )+S2 

    即从链表头结点到入环点的距离,等于从首次相遇点绕环n-1圈再回到入环点的距离。这样一来,只要把其中一个指针放回到头节点位置,另一个指针保持在首次相遇点,两个指针都是每次向前走1步。那么,它们最终相遇的节点,就是入环节点。

     

        public Node getCycleEntrance(Node node) {
            //快指针,每次走2步
            Node fast = node;
            //满指针,每次走1步
            Node low = node;
    
            boolean hasCycle = false;
    
            //获取第一次相遇节点fast
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                low = low.next;
    
                //快慢指针相遇,存在环
                if (fast == low) {
                    hasCycle = true;
                    break;
                }
            }
    
            //无环直接返回
            if (!hasCycle) {
                return null;
            }
    
            //指向头节点
            Node head = node;
            //指向第一次相遇节点
            Node counter = fast;
            while (head != null && counter != null) {
                if (head == counter) {
                    return head;
                }
                head = head.next;
                counter = counter.next;
            }
    
            return null;
        }

     

    展开全文
  • 判断给定的链表中是否有环。如果有环则返回true,否则返回false。 你能给出空间复杂度的解法么? 输入 无 输出 无 思路: 快慢指针判断法:设置两个指针,从同一个起点出发,一个速度为2个节点/次,一个速度为1个...

    题目

    判断给定的链表中是否有环。如果有环则返回true,否则返回false。
    你能给出空间复杂度 O(1) 的解法么?

    在这里插入图片描述

    输入

    输出

    思路:

    快慢指针判断法:设置两个指针,从同一个起点出发,一个速度为2个节点/次,一个速度为1个节点/次,
    如果这个链表内不存在环。那么慢指针永远追不上快指针,直到快指针先遍历到NULL,退出循环,判断结束,输出false
    如果这个链表内存在环,那么慢指针和快指针一定会一直绕环移动,并且某个时刻一定会重合,此时判断结束,输出true

    为什么一定会相遇??,我们假设环的长度为L(L>=2)
    快指针速度是2,慢指针速度为1,设运动时间为t,O是参照起点
    慢指针点是M,快指针点是F,假设初始位移OF=x1,OM=x2,顺时针为正方向
    则经过t 时间后,快指针 OF = (2 * t + x1) % L
    经过t 时间后 ,慢指针 OM = ( t + x2 ) % L
    那是否存在 t 使 (2 * t + x1) % L =( t + x2 ) % L ?
    即判断 (2 * t + x1) 三( t + x2 ) mod L 是否存在实数解 t
    这个式子等价于:(2 * t + x1 - (t + x2)) mod L = 0 (看不懂这个式子就再去看看模的定义)
    化简:( t + x1 - x2 ) mod L = 0
    肯定有解,傻瓜都知道有解!!!
    所以快慢指针肯定会相遇,所以只需要判断快慢指针是否相遇就可以知道该链表有没有环了;
    在这里插入图片描述

    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public boolean hasCycle(ListNode head) {
            ListNode f = head;
            ListNode m = head;
            while(f!=null && f.next!=null){
                f = f.next.next;
                m = m.next;
                if(f==m) return true;
            }
            return false;
        }
    }
    
    展开全文
  • 如何判断链表有环

    2020-01-17 17:29:50
    时间复杂度O(n),空间复杂度O(1)。方法一、穷举遍历 方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次...

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

    不允许修改链表结构。
    时间复杂度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;
    }

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

    方法四、Set集合大小变化
    评论中有 @长沙小辣椒 同学指出:还可以用 set 遍历链表,把节点放入set里,每次访问下个节点时,如果set长度不变,则跳出,说明有环。否则set长度+1,继续遍历。

    该方法时间复杂度是O(N),空间复杂度上因为需要额外等数量的存储空间,所以空间复杂度是O(n)。

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

    当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;
    }

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


    方法一、直接法
    直接判断第一个链表的每个结点是否在第二个链表中,时间复杂度为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个结点,然后两个链表再开始比较。

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

    参考资料
    漫画算法:如何判断链表有环?
    判断两个单链表是否相交
    数据结构面试 之 单链表是否有环及环入口点 附有最详细明了的图解
    链表中环形的入口
    【单链表】环的入口点 原理理解!
    如何判断单链表是否有环、环的入口、环的长度和总长

     

    如何寻找环入口?
    我们先假设链表长度为N,环长度为n,那么我们就可以直接计算出快慢指针的相遇节点:

    一、当n>=N/2时,快慢指针相遇第n个节点

    证明,可推理出此时慢指针必然在环内,慢指针走了n步时,快指针走了2n步,比慢指针多走了n步,正好绕环一周回到 n节点,故此时相遇。

    二、当n<N/2时,快慢指针相遇在 第(N-N%n)个节点

    证明,由于 N%n<n,故此时慢指针已在环内,快指针比慢指针多走了(N-N%n)步,而(N-N%n)必然是 n的倍数,故 快指针 只比慢指针多绕环走了几整圈而已,此时快慢指针相遇。

     

    那么我们说了上面这么多有什么用呢?我们实际上并不知道N和n的值为多少,但是我们通过判断有环的操作时实际上已经找到了快慢指针的相遇节点,也就是刚刚所说的 n节点或者(N-N%n)节点,我们简单点就称之为 m节点吧。

    由刚才的分析可知m节点有个特点,那就是在m节点往下接着走m步最终还是回到m节点。那么我们利用这个特性,让快指针回到起点,慢指针仍然待在m节点,两个指针同时开始走,每次都只走一步。因为两个指针走m步后都会走到m节点,那么当它们第一次相遇时就必然是在环的起点。

    还是比较好理解的是吧。哈哈看代码:

    Node *getCircleHead(Node *node){
        //先判读是否有环
        if (hasCircle(node)) {
            
            Node *fast=node;
            Node *slow=node;
            
            //找到交点m
            do{
                fast=fast->next->next;
                slow=slow->next;
            }while (fast!=slow);
            
            //找环入口
            fast=node;
            while (fast!=slow) {
                fast=fast->next;
                slow=slow->next;
            }
            return fast;
        }
        return NULL;
    }

     


    如何推导出n和N-N%n呢?

    首先我们假设链表长为N,环长度为n,非环部分长度m=N-n。

    当慢指针走过m长度时,此时慢指针刚进入环,快指针走过2m。

    由于快指针已经进入环内,可知快指针已经在环内走了2m-m=m步,当然由于环的长度为n,而且我们不知道m与n的大小关系,此时快指针应该在环的m%n的位置。

    那么快指针还有差多少距离就能赶上慢指针了呢?快指针距离走完整个环有 (n-m%n)%n的长度(同时也是距离慢指针的距离),也就是说快指针再走2*((n-m%n)%n)就可以赶上慢指针了。

     

    OK,我们再来看慢指针,根据上面的推导可以知道,慢指针走的距离为 d=m+(n-m%n)%n。

    1. 先看n-m%n,必然可知 0<n-m%n<=n,当且仅当m==n时,满足 n-m%n=n,所以将 m=n带入 d=m+(n-m%n)%n,得到 d=n;

    2. 由上面可知,当 m!=n时,0<n-m%n<n ,所以 (n-m%n)%n=n-m%n ,d= m+n-m%n =m+n-m%n,再分两种情况

       (1)m<n时,d=m+n-m=n;

       (2)m>n时,d=m+n-m%n=N-(N-n)%n=N-N%n;

    最后综合上面结论可知

       (1)m<=n时,d=n;

       (2)m>  n时,d=N-N%n;

    推导稍微有点复杂,建议朋友们自己画个图,比较容易理解。

     

    这个时候我们把d求出来以后,可以得到一个非常有意思的特性,从d节点开始往下再走d个节点,仍然能够走回到d点,证明:

    当 m <= n 时,d = n,因为此时环的长度就为n,所以走d步还是回到原点。

    当 m > n 时 , d = m + n - m%n ,

                            d%n = m%n + n%n - m%n = 0,证明又回到了原点。

     

    展开全文
  • 判断链表有环

    2020-12-06 11:25:58
    在此基础上,本节带领大家讨论一个问题:如何判断一个单链表中有环?注意,有环链表并不一定就是循环链表。循环链表指的是“首尾相连”的单链表,而环链表则指的是单链表中存在一个循环子链表,如图 1 所示。图 1 ...
  • 判断链表有环

    2021-10-27 10:40:48
    开始循环,让p1每次向后移动1个节点,p2每次向后移动2个节点,比较两个指针指向的节点是否相同,如果相同,则可以判断链表有环,如果不同,则继续循环 分析: 假设链表的节点数量为n,则该方法的时间复杂度为O(n),...
  • 如何判断链表有环摘自漫画算法:题目:一个单向链表,链表中可能出现“”,就像下图这样,那么如何用程序来判断该链表是否为环链表呢?方法1首先从头节点开始,以此遍历单链表中的每一个节点。每遍历一个新...
  • 链表插入操作的时间复杂度真的是O(1)吗?

    万次阅读 多人点赞 2019-01-24 22:29:34
    提起链表,很多人可能都会知道它的优势就是能够快速插入、删除数据。但是往链表中插入数据的时间复杂度真的是O(1)吗?相信看完这篇文章,读者会自己的答案了。为什么用一节来讲解链表代码实现 ...
  • 题目描述:  一个单向链表,链表当中可能出现“”。如何用程序判断出这个链表是环链表? ...【1】【算法】如何判断链表有环 地址:https://blog.csdn.net/u010983881/article/detai...
  • 判断链表是否有环--三种思路

    万次阅读 2020-03-24 18:12:53
    给定一个链表,判断链表中是否有环。 注:这个可以是尾节点连接到前面的任意一个节点 0x02.分析三种方法 第一种:哈希表 最容易想到的,就是每遇到一个节点,如果不存在,就把它存入哈希表,存在就直接返回true。...
  • 如何判断链表有环? 1,什么是环链表? 一个有环的链表 :eg. A->B->C->D->B->C->D 如图: 2,如何判断链表有环? 第一种方法:遍历:出现两个相同节点则证明出现,利用HashSet存放已遍历...
  • 如何判断链表有环

    2019-04-03 00:31:30
    如果一个单向链表链表当中可能出现"",就像下图这样,如何判断这个链表环链表? 方案一:暴力法 从头节点,依次遍历单链表的每一个节点,每到一个新的节点就头节点重新遍历之前的所有的节点,对比...
  • 供大家交流使用,欢迎大家交流指对。。。欢迎大家下载。。
  • 判断链表中是否有环

    2021-11-22 08:09:55
    判断给定的链表中是否有环。如果有环则返回true,否则返回false。 数据范围:链表长度 0≤n≤10000,链表中任意节点的值满足 ∣val∣<=100000 要求:空间复杂度 O(1),时间复杂度 O(n) 输入分为2部分,第一部分为...
  • 详解:如何判断链表中是否有环

    千次阅读 2021-08-23 15:55:18
    如何判断链表中是否有环是一道非常经典的题目,下面用3种方法实现。 方法一:暴力双重循环 直接使用双重循环,没什么好讲的。 方法二:使用HashSet 在方法一的基础上进行优化降低复杂度,使用hashSet作为额外缓存,...
  • 判断链表是否有环1. 判断链表是否有环2. 如果有环,如何找到这个的入口 题意: 给定一个链表,返回链表开始入的第一个节点。 如果链表无,则返回 null。 主要考察两知识点: - 判断链表是否 - 如果有环,...
  • 为此,我觉得必要专门开几篇文章写写链表相关的内容,但是如果从零开始写起太过于枯燥,文章也会变得冗长,所以本文只写一些总结性的内容,对其中的原理不深究。 另外,本文默认使用节点Node的C++定义为: ...
  • 方法一、穷举遍历 时间复杂度是 O(N *2), 空间复杂度是 O(1)的 方法二、哈希表缓存 时间复杂度是O(N),空间复杂度是 O(N)的 方法二、快慢指针法 时间复杂度是O(N),空间复杂度是 O(1)的
  • 一、时间复杂度和空间复杂度 1、什么是算法效率? 算法效率分为时间效率和空间效率,时间效率被称为时间复杂度而空间效率称为空间复杂度; 时间复杂度是主要衡量一个算法的运行速度,而空间复杂度主要衡量的是算法...
  • 判断链表是否有环

    2021-01-22 14:02:38
    链表是否有环? 首先了解自定义双向链表的实现: ...先解释下有环的概念,有环的意思就是说,链表尾的下一个节点接回了头节点,这样导致了该链表会循环,永无尽头。...定义一个checkCycle方法,判断是否有环
  • 给定一个链表的头节点 head,返回链表开始入的第一个节点。如果链表,则返回null。如果链表某个节点,可以通过连续跟踪 next 指针...面试思路:时间复杂度O(logn),空间复杂度Olog(1) class Solution...
  • 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表中的,评测系统内部使用整数 pos 来表示链表尾连接到链表中的...
  • 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在。 为了表示给定链表中的,评测系统内部使用整数 pos 来表示链表尾连接到链表中的...
  • 如何判断链表有环1、题目分析方法一方法二方法三【双指针】2、代码实现 1、题目分析 一个单向链表,链表中可能出现“”,就像下图这样。如何用程序来判断该链表是否为环链表呢? 方法一 方法流程: 从头...
  • NC4判断链表中是否有环 判断给定的链表中是否有环。如果有环则返回true,否则返回false。 数据范围:链表长度,链表中任意节点的值满足 要求:空间复杂度,时间复杂度 思路1:哈希表(时空复杂度都是):遍历链表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,041
精华内容 8,416
关键字:

判断链表有环时间复杂度