精华内容
下载资源
问答
  • 寻找链表(C++)

    2020-04-04 19:19:16
    //寻找链表 ListNode* FindLink(ListNode* head) { if(head == nullptr) return nullptr; ListNode* slow = head->next; if(slow == nullptr) return nullptr; ListNode* fast = ...
    //寻找链表的环
    ListNode* FindLink(ListNode* head)
    {
        if(head == nullptr)
            return nullptr;
        ListNode* slow = head->next;
        if(slow == nullptr)
            return nullptr;
        ListNode* fast = slow->next;
        while(fast != nullptr)
        {
            if(fast == slow)
                break;
            fast = fast->next;
            slow = slow->next;
            if(fast == nullptr)
                return nullptr;
            fast = fast->next;
        }
        if(fast == nullptr)
            return nullptr;
        else
        {
            slow = head;
            while(fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }
               return fast;
        }
    }
    
    
    int main()
    {
        //链表A
        ListNode* l11 = new ListNode(1);
        ListNode* l12 = new ListNode(3);
        ListNode* l13 = new ListNode(5);
        ListNode* l14 = new ListNode(7);
        ListNode* l15 = new ListNode(9);
        ListNode* l16 = new ListNode(11);
        ListNode* l17 = new ListNode(13);
        l11->next = l12;
        l12->next = l13;
        l13->next = l14;
        l14->next = l15;
        l15->next = l16;
        l16->next = l17;
        l17->next = l14;
        //链表B
        ListNode* l21 = new ListNode(2);
        ListNode* l22 = new ListNode(4);
        ListNode* l23 = new ListNode(6);
        ListNode* l24 = new ListNode(8);
        ListNode* l25 = new ListNode(10);
        l21->next = l22;
        l22->next = l23;
        l23->next = l24;
        l24->next = l25;
        ListNode* link = FindLink(l11);
        cout<<link->val<<endl;
        return 0 ;
    }

     

    展开全文
  • 给一个链表,若其中包含,请找出该链表的入口结点,否则,输出null。 分析: 快慢指针 设快慢指针,fast,slow,快慢指针初始都指向链表头部,快指针每次走两步,慢指针每次走一步,若链表,快指针会走到...

    题目描述

    给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
    在这里插入图片描述
    分析: 快慢指针

    1. 设快慢指针,fast,slow,快慢指针初始都指向链表头部,快指针每次走两步,慢指针每次走一步,若链表没环,快指针会走到链表末尾。若链表存在环,那么快慢指针一定会在环内的某个结点相遇,因为快指针每次走两步,比慢指针快一步,所以早晚会赶上慢指针然后相遇。
    2. 我们设 不含环的链表部分结点数为 a(不含入口结点),环链表的部分结点数为 b.
      假设 第一次快慢指针第一次相遇时,慢指针走了 x 步,那么快指针就走了 2x 步, 两指针一共走的步数为 S ,S = 3x.
      快慢指针相遇时,去掉两者没入环之前都会走的 a 个结点,快指针会在环里比慢指针多走 m 个环,m 为一常数,
      即 2x - mb = x ==》 x = mb,相当于在快慢指针第一次相遇时,慢指针走了 m 个环的长度,快指针走了2m个环的长度。
    3. 题目是要找环的入口, 我们假设慢指针从头走了 k 步,那么走到链表入口结点的步数就可以这样表示 k = a + kb,k为任意常数, 在环内绕了m圈走到入口节点,那么目前慢指针已经走了 mb 个结点,令 k = m , 那么此时慢指针再走个 a 步,就可以回到环的入口节点,为了找到入口节点,我们在快慢指针第一次相遇后,定义一个指针指向链表头部,每次走一步,和慢指针一起向前走 a 步后相遇,相遇的结点就是入口节点。
      python 解法:
    def detectCycle(head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #定义快慢指针
        fast,slow = head,head
        while fast :
             #快指针走到链表尾,不存在环
            if not (fast and fast.next and fast.next.next):
                return 
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                #快慢指针第一次相遇后,定义一个指向头结点的指针,每次走一步
                start = head 
                while start != slow:
                    start = start.next
                    slow = slow.next
                #找到环入口结点
                return start
    

    java 解法:

    /*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            ListNode fast = pHead;
            ListNode slow = pHead;
            while(true){
                if (fast == null || fast.next == null || fast.next.next == null){
                    return null;
                }
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
                    ListNode start = pHead;
                    while(start != slow){
                        start = start.next;
                        slow = slow.next;
                    }
                    return start;
                }
            }
        }
    }
    
    展开全文
  • 示例可参考博客:判断链表中是否有,解法与该题类似,需要先判断是否有,若有才能进行寻找入环节点的步骤,否则就直接返回NULL了。 那如何寻找入环节点呢,方法也不复杂,与第4题类似。在判断出链表之后,...

    声明:题目来源:力扣(LeetCode)

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL 。

    题目链接:环形链表II

    说明:不允许修改给定的链表。
    示例可参考博客:判断链表中是否有环,解法与该题类似,需要先判断是否有环,若有环才能进行寻找入环节点的步骤,否则就直接返回NULL了。
    那如何寻找入环节点呢,方法也不复杂,与第4题类似。在判断出链表有环之后,计算出环的长度,再设置快慢两个指针,快指针先走一个环的长度,慢指针再和快指针同时走,两者相遇的位置即为环的入口。
    参考代码如下:

    struct ListNode *detectCycle(struct ListNode *head) {
        if(head == NULL){
            return NULL;
        }
        struct ListNode *pre = head;
        struct ListNode *lag = head;
        while(pre){
            lag = lag->next;
            pre = pre->next;            
            if(pre){
                pre = pre->next;
            }       
            if(lag == pre){
                break;
            }
        }
        if(pre == NULL){
            return NULL;
        }
        struct ListNode *pre2 = head;
        do{
            pre2 = pre2->next;
            lag = lag->next;
            pre = pre->next;            
            pre = pre->next;        
        }while(lag != pre);
        lag = head;
        while(pre2 != lag){
            lag = lag->next;
            pre2 = pre2->next;
        }
        return lag;
    }
    

    上面的代码是正常人写的,但是这种方法还可以优化,不过需要我们使用数学方法来推导。
    在这里插入图片描述
    如图,假设入环前的节点有 L1 个,相遇点距入口有 L2 个,环有 N 个节点,fp 在环内走了 k1 圈,sp 在环内走了 k2 圈,那么 fp 与 sp 相遇时两者走过的路劲长度应满足:
    在这里插入图片描述
    消去 fp、sp 的路程,解出:

    L1 + L2 = kN,k为正整数

    也就是说,若有指针从表头出发,它走到入口时,相当于走了kN - L2的长度,这个长度,刚好也可以使 fp 或 sp 从相遇的位置走到入口。
    于是求环长度的步骤可以省略,当 fp 与 sp 相遇时,使一个指针从表头出发,另一个指针也同时与之从 fp、sp 相遇点出发,这两个指针相遇时的节点,即为环的入口节点。

    以下是学数学的人写的代码:

    struct ListNode *detectCycle(struct ListNode *head) {
        if(head == NULL){
            return NULL;
        }
        struct ListNode *pre = head;
        struct ListNode *lag = head;
        while(pre){
            lag = lag->next;
            pre = pre->next;            
            if(pre){
                pre = pre->next;
            }
            if(lag == pre){
                break;
            }       
        }
        if(pre == NULL){
            return NULL;
        }
        lag = head;
        while(pre != lag){
            lag = lag->next;
            pre = pre->next;
        }
        return lag;
    }
    
    展开全文
  • 2-11寻找链表中

    2020-02-29 16:03:04
    传入一个头节点判断链表是否有,如果有返回第一个入的节点,如果没有返回null。 解题方法1 可以使用哈希表来完成,每遍历一个节点就把该节点的引用存储到哈希表,如果哈希表出现了重复的引用,那么那个...

    题目描述

    • 传入一个头节点判断链表是否有环,如果有环返回第一个入环的节点,如果没有环返回null。

    解题方法1

    • 可以使用哈希表来完成,每遍历一个节点就把该节点的引用存储到哈希表,如果哈希表中出现了重复的引用,那么那个重复的引用就是第一个入环的节点。如果没有出现重复的引用说明没有环。
    public class Test {
        public static void main(String[] args) throws Exception {
             int[] arr1 = {2,3,4,5};
             Node head1 = create1(arr1);
             Node head2 = create2(arr1);
             Node n1 = ishuan(head1);
             Node n2 = ishuan(head2);
            System.out.println(n1);
            System.out.println(n2.val);
        }
        //判断链表是否有环
        public static Node ishuan(Node head){
            HashSet<Node> set = new HashSet<>();
            for(Node p=head.next;p!=null;p=p.next){
                if(set.contains(p)){
                    return p;
                }
                else{
                    set.add(p);
                }
            }
            return null;
        }
        //创建一个无环单链表
        public static Node create1(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            return head;
        }
        //创建一个有环单链表
        public static Node create2(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            lastnode.next = head.next; //这里让尾节点指向第一个节点
            return head;
        }
    }
    class Node{
        int val;
        Node next;
        Node(int val){
            this.val = val;
        }
    }
    
    • 算法的时间复杂度为n,空间复杂度为n。

    解题方法2

    • 我们可以使用快慢指针法进行优化,使得空间复杂度为1。
    • 定义一个慢指针slow一个快指针fast,慢指针每次移动一步,快指针每次移动两步。如果无环快指针会首先到达终点,如果有环快慢指针会相遇。
    • 需要注意的是,我们不仅要判断它是否有环,还要找出第一个入环的节点。这个寻找的过程还是比单纯判断是否有环麻烦一点。
    • 首先让两个指针都指向第一个节点,然后分别移动两个指针,当快指针到达终点说明无环返回null。
    • 当快指针和慢指针再一次相遇说明有环。此时将快指针指向第一个节点,并改为一次移动一步,慢指针照常移动,那么下次两指针相遇的地方就是第一个入环的节点。
    • 证明如下:设链表无环部分长度为a,有环部分长度为b,两指针第一次相遇的位置距离入环口为x。
      在这里插入图片描述
    • 如,上图可以证明a = b-x。那么当两指针在x处相遇时慢指针再走b-x的距离可以到达环口且链表初始点距离环口为a,此时把快指针指向开头并调整速度为1由于a = b-x,那么它们必然会在环口相遇。
    • 代码如下
    public class Test {
        public static void main(String[] args) throws Exception {
             int[] arr1 = {2,3,4};
             Node head1 = create1(arr1);
             Node head2 = create2(arr1);
             Node n1 = ishuan(head1);
             Node n2 = ishuan(head2);
            System.out.println(n1);
            System.out.println(n2.val);
        }
        //判断链表是否有环
        public static Node ishuan(Node head){
            Node slow = head.next;
            Node fast = head.next;
            int i = 0;
            //第一次循环 如果无环返回null
            while (slow!=null&&fast!=null){
                if(fast.next==null){
                    return null;
                }
                if(i>0 && slow==fast){
                    break;
                }
                fast = fast.next.next;
                slow = slow.next;
                i++;
            }
            if(fast==null){
                return null;
            }
            //第二次循环 调整fast指针 寻找入环口节点并返回
            fast = head.next;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        //创建一个无环单链表
        public static Node create1(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            return head;
        }
        //创建一个有环单链表
        public static Node create2(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            lastnode.next = head.next; //这里让尾节点指向第一个节点
            return head;
        }
    }
    class Node{
        int val;
        Node next;
        Node(int val){
            this.val = val;
        }
    }
    
    展开全文
  • 寻找链表环的问题

    千次阅读 2018-04-12 19:20:07
    寻找链表环的问题 一、简介 这篇博客主要介绍判断链表是否存在环、寻找环的入口点和计算链表的长度的解决方案,主要是介绍思想,不涉及代码。(因为本萌新的师傅一直教育思想的重要性) 这里主要介绍三种解决...
  • 偶然发现很多文章和牛客、leetcode上的说明都是错的, 大部分的公式貌似都...假设链表头结点到的头结点长度为A 的头结点到第一次相遇的结点距离为B, 的长度为 R 那么 slow走过的距离为 A + B, fast走过的...
  • 代码题--C++--判断单链表其中是否有寻找链表结点 题目:给定一个单链表,(1)判断其中是否有,(2)寻找链表结点。 1.判断时候有(链表头指针为head) 对于这个问题我们可以采用“快慢指针”的...
  • 寻找链表环的入口

    万次阅读 多人点赞 2019-06-11 16:53:12
    寻找链表环的入口) 题解: 这个连同I都是很经典的题啦,刷CC150时候就折磨了半天。 其实就推几个递推公式就好。。首先看图(图引用自CC150): 从链表起始处到环入口长度为:a,从环入口到Faster和Slower相遇点...
  • 链表寻找环入口

    2021-03-31 18:58:08
    链表寻找环入口 #mermaid-svg-JWpRPnYJFwJDkcyw .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-JWpRPnYJFwJDkcyw .label text{...
  • 我们先来了解一下查找链表入口点常用的方法。 即使用快慢指针来解决该问题 public Entry loopEntry(){ if(headEntry == null || headEntry.next == null){ return null; } if(headEntry.next == ...
  • M142.寻找链表环入口

    2019-11-14 11:35:16
    为了表示给定链表中,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有。 说明:不允许修改给定的链表。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ...
  • 快指针fast走两步,慢指针slow走一步,如果相遇就是带环链表; 然后让cur1从链表头开始走,cur2从相遇点开始走,再次相遇的位置就是入的第一点 public class DateCycle { static class ListNode { int val; ListNode...
  • Given a linked list, determine if ...题目是判断链表里面是否有循环,可以使用快慢指针解决,实际上只要是判断循环的题目都可以使用快慢指针解决, 慢指针每一次走一格,快指针每一次走两格,当快指针为null的时候肯
  • 为了表示给定链表中,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个...
  • 寻找链表环入口

    2014-03-31 18:21:48
    1.如何判断链表?  同时用两个指针p1、p2指向表头,每次循环p1指向后继,p2指向后继的后继(即p2的速度是p1的两倍);循环的结束条件是,p2后继为空(无)或p1==p2(有)。 2.如何证明这两点一定会相遇呢?...
  • 为了表示给定链表中,我们使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果pos是-1,则在该链表中没有。 说明:不允许修改给定的链表。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ...
  • 判断链表中是否有链表中环的长度 求的入口节点的位置 带环链表的长度 解法: 判断是否有: 可以利用快慢指针追赶的方式,即设定两个指针,slow、fast,slow指针每次走一步,fast指针每次走两步,如果存在...
  • # 为了表示给定链表中,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有。注意,po # s 仅仅是用于标识的情况,并不会作为参数传递到函数。 # #...
  • /*:在一个单链表存在一个循环子链表,有两种解题思路 思路一:从当前head出发,每前进一步就往回比较所有前驱节点,看是否是相同节点,若是则存在、 思路二:定义快慢指针,快指针每次走两步,慢指针每次走...
  • 如果链表,请找出入口。  3. 计算的大小。 思路:快慢指针  分别定义一个快指针fast和慢指针slow,快指针一次走两步,慢指针一次走一步。如果链表没有,那么fast最终会指向nullptr;如果链表...
  • 一个链表中包含,请找出该链表的入口结点 个人思路分析 一定要保证思维有序,分析问题后即使最后没有得到最完美的答案,至少方向正确不能跑偏。 链表结构 public class ListNode { int val; ...
  • 这个跟寻找环的题目相似,但是难度增加了。花费了较多时间去做。 肯定是利用快慢指针找出是否存在。画图之后发现,慢指针走的步数是的长度。所以,只要另一个指针从开头出发,慢指针继续向前走,他们碰到的节点...
  • 看了好多思路都是各种证明,假设ab两个点,a移动速度是b的2倍,都是b到入点的时候各种条件,相遇时各种条件,然后a以b的速度从头走又是各种假设,最后证明相遇的点就是入口。 现在不用数学公式证明,不知道有没有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,364
精华内容 5,345
关键字:

寻找链表中的环