精华内容
下载资源
问答
  • 判断一个单链表是否有环: 方法1: 使用hash_map,当map中出现重复的值时,该值即为环的第一个节点。 方法2: 两个指针,快指针一次走两步,慢指针一次走一步,当快慢指针相遇时,将快指针放于head位置,快指针...

    判断一个单链表是否有环:

    方法1:

     使用hash_map,当map中出现重复的值时,该值即为环的第一个节点。

    方法2:

    两个指针,快指针一次走两步,慢指针一次走一步,当快慢指针相遇时,将快指针放于head位置,快指针由一次走两步变成一次走一步,快指针和慢指针一定会在第一个入环节点处相遇。。

     

     

    判断两个链表是否相交:

    方法1:使用map,将链表1全部加入map中,然后依次查找链表2的节点是否在map中,若在,即为两个链表相交。

    方法2:先遍历链表1,得到链表1 的长度和链表1的最后一个节点。再遍历链表2,得到链表2 的长度和链表2 的最后一个节点。

    若链表1和链表2 的最后一个节点内存地址是否相等。如果end1的地址和end2的地址不相同,则不相交。

    如果相等则相交,若链表1的长度为100,链表2的长度为80,则链表1 先走20步,然后链表1和链表2 一起走,他们一定会走到共同的相交处。

     

    如果一个链表有环,一个链表无环,则不可能相交。

    展开全文
  • 用python 判断一个单链表是否有环

    千次阅读 2019-01-27 11:57:04
    用python 判断一个单链表是否有环. 思路1: 判断一个单链表是否有环, 可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面. 其实 可以遍历这个单链表, 访问过后, 如果这个节点 不在 set 里面, 把这...

    用python 判断一个单链表是否有环.

    https://leetcode.com/problems/linked-list-cycle/

    思路1:

    判断一个单链表是否有环,
    可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.
    其实 可以遍历这个单链表, 访问过后,
    如果这个节点 不在 set 里面, 把这个节点放入到 set 集合里面.
    如果这个节点在 set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环
    如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    """
    @Time    : 2019/1/12 00:59
    @File    : has_circle.py
    @Author  : frank.chang@shoufuyou.com
    
    https://leetcode.com/problems/linked-list-cycle/
    
    
    141. Linked List Cycle
    Easy
    
    1231
    
    93
    
    Favorite
    
    Share
    Given a linked list, determine if it has a cycle in it.
    
    To represent a cycle in the given linked list,
    we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
    If pos is -1, then there is no cycle in the linked list.
    
    
    
    Example 1:
    
    Input: head = [3,2,0,-4], pos = 1
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the second node.
    
    
    Example 2:
    
    Input: head = [1,2], pos = 0
    Output: true
    Explanation: There is a cycle in the linked list, where tail connects to the first node.
    
    
    Example 3:
    
    Input: head = [1], pos = -1
    Output: false
    Explanation: There is no cycle in the linked list.
    
    
    
    
    Follow up:
    
    Can you solve it using O(1) (i.e. constant) memory?
    
    Accepted
    340,579
    Submissions
    971,443
    
    """
    class LinkNode:
    
        def __init__(self, value):
            self.value = value
            self.next = None
    
    
    class Solution1:
        """
        思路分析:
        判断一个单链表是否有环,
        可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.
        其实 可以遍历这个单链表, 访问过后,
        如果这个节点 不在 set  里面, 把这个节点放入到 set 集合里面.
        如果这个节点在  set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环.
    
        如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.
    
        """
    
        def hasCycle(self, head):
    
            mapping = set()
    
            flag = False
    
            p = head
    
            while p:
    
                if p not in mapping:
                    mapping.add(p)
                else:
                    flag = True
                    break
                p = p.next
    
            return flag
    

    还有一个解决方案:

    定义 两个指针, 一个快指针fast, 一个慢指针slow, 快指针一次走两步,慢指针一次走一步.
    如果 两个指针相遇了, 则说明链表是有环的.
    如果 fast 都走到null了, 还没有相遇则说明没有环.

    为什么是这样呢? 简单分析一下?
    图1

    图片2

    图片3

    图片4
    图片5

    图片6

    图片7
    用图形来分析一下,这样可以清晰一点.

    图形分析

    因为快指针 先走 所以快指针先进入环,之后慢指针后进入环, 无论如何,

    最后 要么 慢指针进入环的时候, 快指针可能已经走了 很多遍环, 也有可能没有走完环. 但无论如何 当慢指针 进入环的时候,
    fast 有可能在 慢指针的后面, 或者前面, 无论如何 快指针 是必慢指针走的快的 , 所以 只要有环 一定可以 和慢指针来一次相遇.

    你可能想 会不会错过呢?
    答案 是不会的. 你想 快指针一次 走两步, 慢指针一次都一步.
    假设 这是一条无穷尽的单链表. 他们 每走一步, 两者之间的距离就减1, 所以 只要链表足够长, 是一定会相遇的.

    看下图:
    图片8

    class Solution:
        """
        定义 两个指针, 一个快指针fast, 一个慢指针slow,  快指针一次都两步,慢指针一次走一步. 
        如果 两个指针相遇了, 则说明链表是有环的. 
        如果 fast 都走到null了, 还没有相遇则说明没有环. 
        """
    
        def hasCycle(self, head):
    
            flag = False
            if head is None or head.next is None or head.next.next is None:
                return flag
    
            fast = head.next.next
            slow = head.next
    
            while fast is not slow:
    
                if fast.next is None or fast.next.next is None:
                    # no circle
                    return flag
                fast = fast.next.next
                slow = slow.next
    
            # 相遇肯定有环
            if fast is slow:
                # hasCircle
                flag = True
    
            return flag
    

    第二次做DAY20201130

    闲下来 之前的代码 写的不够优雅,今天 重新修改了一下 之前的代码,这样写看起来 比 之前的代码 稍微 好看一点,详细请看下面

    141. 环形链表

    给定一个链表,判断链表中是否有环。

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

    如果链表中存在环,则返回 true 。 否则,返回 false

    进阶:

    你能用 O(1)(即,常量)内存解决此问题吗?

    示例 1:

    img

    输入:head = [3,2,0,-4], pos = 1
    输出:true
    解释:链表中有一个环,其尾部连接到第二个节点。
    

    示例 2:

    img

    输入:head = [1,2], pos = 0
    输出:true
    解释:链表中有一个环,其尾部连接到第一个节点。
    

    示例 3:

    img

    输入:head = [1], pos = -1
    输出:false
    解释:链表中没有环。
    

    提示:

    • 链表中节点的数目范围是 [0, 104]
    • -105 <= Node.val <= 105
    • pos-1 或者链表中的一个 有效索引

    方法1 路径记录法

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            visited = set() 
            while head:
                cur = head
                if cur not in visited:
                    visited.add(cur)
                else:
                    return True
                head = head.next 
            return False 
    
     
    class Solution02:
        def hasCycle(self, head: ListNode) -> bool:
            seen = set()
            while head:
                if head in seen:
                    return True
                seen.add(head)
                head = head.next
            return False
    
    

    方法2 快慢指针法

    第1种解法
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            if not head:
                return False 
    
            slow = head 
            fast = head.next 
    
            while fast and fast.next:
                if fast ==slow:
                    return True 
                fast= fast.next.next 
                slow = slow.next 
                
            return False 
    
    另一种写法
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            if head is None or  head.next is None:
                return False 
            
            slow = head 
            fast  =head.next 
            while slow != fast:    
                if fast is None or fast.next is None:
                    return False 
                fast = fast.next.next 
                slow = slow.next 
    
            return True 
    
    分享感动,留住快乐. 2019-01-27 11:53:45 --frank
    展开全文
  • 20170515_判断一个单链表是否有环

    20170515_判断一个单链表是否有环

    转自:http://www.cnblogs.com/zhyg6516/archive/2011/03/29/1998831.html


    这题目还是慢有意思的。

    题目:

    0.如何判断单链表里面是否有环?

    算法的思想是设定两个指针p, q,其中p每次向前移动一步,q每次向前移动两步。那么如果单链表存在环,则p和q相遇;否则q将首先遇到null。
    这里主要理解一个问题,就是为什么当单链表存在环时,p和q一定会相遇呢?


    假定单链表的长度为n,并且该单链表是环状的,那么第i次迭代时,p指向元素i mod n,q指向2i mod n。因此当i≡2i(mod n)时,p与q相遇。而i≡2i(mod n) => (2i - i) mod n = 0 => i mod n = 0 => 当i=n时,p与q相遇。这里一个简单的理解是,p和q同时在操场跑步,其中q的速度是p的两倍,当他们两个同时出发时,p跑一圈到达起点,而q此时也刚好跑完两圈到达起点。
    那么当p与q起点不同呢?假定第i次迭代时p指向元素i mod n,q指向k+2i mod n,其中0<k<n。那么i≡(2i+k)(mod n) => (i+k) mod n = 0 => 当i=n-k时,p与q相遇。

    解决方案:

    推广:

    1. 如果两个指针的速度不一样,比如p,q,( 0<p<q)二者满足什么样的关系,可以使得两者肯定交与一个节点?

        Sp(i) = pi

        Sq(i) = k + qi

       如果两个要相交于一个节点,则 Sp(i) = Sq(i) =>  (pi) mod n = ( k+ qi ) mod n =>[ (q -p)i + k ]  mod n =0

       =>  (q-p)i + k  = Nn [N 为自然数]

       =>  i = (Nn -k) /(p-q)

       i取自然数,则当 p,q满足上面等式 即 存在一个自然数N,可以满足Nn -k 是 p - q 的倍数时,保证两者相交。

       特例:如果q 是p 的步长的两倍,都从同一个起点开始,即 q = 2p , k =0, 那么等式变为: Nn=i: 即可以理解为,当第i次迭代时,i是圈的整数倍时,两者都可以交,交点就是为起点。

    2.如何判断单链表的环的长度?

       这个比较简单,知道q 已经进入到环里,保存该位置。然后由该位置遍历,当再次碰到该q 位置即可,所迭代的次数就是环的长度。

    3. 如何找到链表中第一个在环里的节点?

       假设链表长度是L,前半部分长度为k-1,那么第一个再环里的节点是k,环的长度是 n, 那么当q=2p时, 什么时候第一次相交呢?当q指针走到第k个节点时,q指针已经在环的第 k mod n 的位置。即p和q 相差k个元素,从不同的起点开始,则相交的位置为 n-k, 则有了下面的图:

    从图上可以明显看到,当p从交点的位置(n-k) ,向前遍历k个节点就到到达环的第一个几点,节点k.

    算法就很简单: 一个指针从p和q 中的第一次相交的位置起(n-k),另外一个指针从链表头开始遍历,其交点就是链表中第一个在环里的交点。

    4. 如果判断两个单链表有交?第一个交点在哪里?

        这个问题画出图,就可以很容易转化为前面的题目。

       

        将其中一个链表中的尾节点与头节点联系起来,则很容发现问题转化为问题3,求有环的链表的第一个在环里的节点。

    1、判断是否有环的代码:

    //141. Linked List Cycle 
    //Given a linked list, determine if it has a cycle in it.
    //Follow up:
    //Can you solve it without using extra space? 
    
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    
    #include<iostream>
    #include<vector>
    using namespace std;
    
    struct ListNode
    {
    	int val;
    	ListNode *next;
    	ListNode(int x):val(x),next(nullptr) {}
    };
    
    ListNode *CreatList(ListNode * &root, vector<int> &a)
    {
    	int n=a.size();
    	if(n==0)
    		return root=nullptr;
    	else
    	{
    		root=new ListNode(a[0]);
    		ListNode *p=root;
    		for(int i=1; i<n; ++i)
    		{
    			ListNode *r=new ListNode(a[i]);
    			p->next=r;
    			p=r;
    		}
    		return root;
    	}
    }
    
    void OutList(ListNode *root)
    {
    	ListNode *p=root;
    	if(p==nullptr)
    		return;
    	else
    	{
    		while(p != nullptr)
    		{
    			if(p->next != nullptr)
    				cout<<p->val<<",";
    			else
    				cout<<p->val<<endl;
    			p=p->next;
    		}
    	}
    }
    
    class Solution
    {
    public:
        bool hasCycle(ListNode *head)	//使用快慢指针来判断单链表是否有环!
    	{
    		ListNode *root=head;
    		if(root == nullptr || root->next == nullptr)
    			return 0;
    		else
    		{
    			ListNode *fast=root;
    			ListNode *slow=root;
    			while( fast != nullptr && fast->next != nullptr)
    			{
    				fast=fast->next->next;
    				slow=slow->next;
    				if(fast == slow)	//快慢指针相遇,有环。
    					return 1;
    			}
    			if(fast == nullptr || fast->next == nullptr)	//快指针到达 nullptr,说明没有相遇,没有环。
    				return 0;
    		}
        }
    };
    
    int main()
    {
    	vector<int> a;
    	int ch;
    	cout<<"依次输入单链表节点数据:"<<endl;
    	while(cin>>ch)
    		a.push_back(ch);
    	cin.clear();
    	cin.sync();
    	ListNode *r;
    	ListNode *root=CreatList(r,a);
    	cout<<"单链表建立完成."<<endl;
    	cout<<"顺序输出单链表:"<<endl;
    	OutList(root);
    	cout<<"顺序输出单链表完成."<<endl;
    
    	Solution example;
    	bool result;
    	result=example.hasCycle(root);
    	cout<<"该单链表有环吗?"<<result<<endl;
    	
    	system("pause");
    	return 0;
    }

    2、寻找环的入口处的代码:

    //142. Linked List Cycle II 
    // Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
    //Note: Do not modify the linked list.
    //Follow up:
    //Can you solve it without using extra space? 
    //寻找环的入口
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    #include<iostream>
    #include<vector>
    using namespace std;
    
    struct ListNode
    {
    	int val;
    	ListNode *next;
    	ListNode(int x):val(x),next(nullptr) {}
    };
    
    ListNode *CreatList(ListNode * &root, vector<int> &a)
    {
    	int n=a.size();
    	if(n==0)
    		return root=nullptr;
    	else
    	{
    		root=new ListNode(a[0]);
    		ListNode *p=root;
    		for(int i=1; i<n; ++i)
    		{
    			ListNode *r=new ListNode(a[i]);
    			p->next=r;
    			p=r;
    		}
    		return root;
    	}
    }
    
    void OutList(ListNode *root)
    {
    	ListNode *p=root;
    	if(p==nullptr)
    		return;
    	else
    	{
    		while(p != nullptr)
    		{
    			if(p->next != nullptr)
    				cout<<p->val<<",";
    			else
    				cout<<p->val<<endl;
    			p=p->next;
    		}
    	}
    }
    
    class Solution
    {
    public:
    	ListNode *detectCycle(ListNode *head)
    	{
    		ListNode *root=head;
    		if(root == nullptr || root->next == nullptr)	//无节点或者只有一个节点时,没有环:
    			return nullptr;
    		else
    		{
    			ListNode *fast=root;	//使用快慢指针来判断单链表是否有环!
    			ListNode *slow=root;
    			while( fast != nullptr && fast->next != nullptr)
    			{
    				fast=fast->next->next;
    				slow=slow->next;
    				if(fast == slow)	//快慢指针相遇,有环:
    				{
    					fast=root;	//fast指针指向X处,slow指针指向Z处,
    								//接下来,这两个指针每次向前走一步,则会在Y处相遇,即环的入口处。
    					while(fast != slow)
    					{
    						fast=fast->next;
    						slow=slow->next;
    					}
    					if(fast == slow)
    						return fast;	//环的入口处。
    				}
    			}
    			if(fast == nullptr || fast->next == nullptr)	//快指针到达 nullptr,说明没有相遇,没有环:
    				return nullptr;
    		}
        }
    };
    
    int main()
    {
    	vector<int> a;
    	int ch;
    	cout<<"依次输入单链表节点数据:"<<endl;
    	while(cin>>ch)
    		a.push_back(ch);
    	cin.clear();
    	cin.sync();
    	ListNode *r;
    	ListNode *root=CreatList(r,a);
    	cout<<"单链表建立完成."<<endl;
    	cout<<"顺序输出单链表:"<<endl;
    	OutList(root);
    	cout<<"顺序输出单链表完成."<<endl;
    
    	Solution example;
    	ListNode *result;
    	result=example.detectCycle(root);
    	
    	system("pause");
    	return 0;
    }




    题目1:给定一个链表,判断它是否有环。
    例如:给出 -21->10->4->5, tail connects to node index 1,返回 true。
    挑战:不要使用额外指针。

    思路:使用两个指针,初始时两个指针均指向链表头位置,然后一个指针每次走两步,一个指针每次走一步,如果在循环过程中遇到两个指针相等,则说明有循环返回 true。如果出现一个指针无法继续往下走,则退出循环返回 false。
    思路的证明:因为 fast 先进入环,在 slow 进入之后,如果把 slow 看作在前面,fast在后面每次循环都向 slow 靠近1,所以一定会相遇,而不会出现 fast 直接跳过 slow 的情况。

    public class Solution{
                public Boolean hasCycle(ListNode head){
                    if(head == null || head.next == null){
                        return false;
                    }
                    ListNode fast, slow;
                    fast = head.next;
                    slow = head;
                    while (fast != slow) {
                        if(fast==null || fast.next==null)
                            return false;
                        fast = fast.next.next;
                        slow = slow.next;
                    } 
                    return true;
                }
            }

    题目2:环的长度是多少?
    方法一:第一次相遇后,让fast停着不走了,slow继续走,记录到下次相遇时循环了几次。
    方法二
    这里写图片描述
    第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b。因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c。我们发现L=b+c=a+b,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度。

    题目3:如何找到环中第一个节点(即Linked List Cycle II)?
    方法:我们已经得到了结论a=c,那么让两个指针分别从X和Z开始走,每次走一步,那么正好会在Y相遇!也就是环的第一个节点。

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null || head.next==null) {
                return null;
            }
    
            ListNode fast, slow;
            fast = head.next;
            slow = head;
            while (fast != slow) {
                if(fast==null || fast.next==null)
                    return null;
                fast = fast.next.next;
                slow = slow.next;
            } 
    
            while (head != slow.next) {
                head = head.next;
                slow = slow.next;
            }
            return head;
        }
    }

    题目4:如何将有环的链表变成单链表(解除环)?
    方法:在上一个问题的最后,将c段中Y点之前的那个节点与Y的链接切断即可。

    题目5: 如何判断两个单链表是否有交点?如何找到第一个相交的节点?
    方法:先判断两个链表是否有环,如果一个有环一个没环,肯定不相交;如果两个都没有环,判断两个列表的尾部是否相等;如果两个都有环,判断一个链表上的Z点是否在另一个链表上。








    展开全文
  • 原文地址:判断一个单链表是否有环及环的链接点(转)作者:蒙恩的罪人给定一个单链表,只给出头指针h: 1、如何判断是否存在环? 2、如何知道环的长度? 3、如何找出环的连接点在哪里? 4、带环链表的长度是多少?  ...

    给定一个单链表,只给出头指针h:

    1、如何判断是否存在环?

    2、如何知道环的长度?

    3、如何找出环的连接点在哪里?

    4、带环链表的长度是多少?

     

    解法:

    1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。

    2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。

    3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。(证明在后面附注)

    4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度

    void Isloop(Llink head)
    {
     if(!head||!head->next)
      return;
     Llink p,q;
     bool loop=false;
     p=q=head->next;
     while(q&&q->next)//判断是否有环
     {
      p=p->next;
      q=q->next->next;
      if(p==q)
      {
       loop=true;
       break;
      }
     }
     if(!loop)
      cout<<"This link has not loopn";
     else
     {
      cout<<"This link has a loopn";
      Llink r=p;
      q=head->next;
      int nonloop=1,loopcount=1;

      //nonloop计算非环结点数,loopcount计算环上结点数
      do//计算环上的结点数
      {
       p=p->next;
       ++loopcount;
      }while(p!=r);
      --loopcount;
      while(p!=q)//得到环的入口结点,同时计算得到非环的结点数
      {
       p=p->next;
       q=q->next;
       ++nonloop;
      }
      --nonloop;
      cout<<"nStart of loop: "<<p->data<<endl;  
      cout<<"nCount of nonloop: "<<nonloop
          <<"nCount of loop: "<<loopcount
          <<"nCount of Linknode: "<<nonloop+loopcount<<endl;
     }
    }

      

    判断是否存在环的程序:

    bool IsExitsLoop(slist *head)  
    1. {  
    2.     slist *slow = head, *fast = head;  
    3.     while ( fast && fast->next )   
    4.     {  
    5.         slow = slow->next;  
    6.         fast = fast->next->next;  
    7.         if ( slow == fast ) break;  
    8.     }    
    9.     return !(fast == NULL || fast->next == NULL);  
    10. }  

     

    寻找环连接点(入口点)的程序:

    slist* FindLoopPort(slist *head)  
    1. {  
    2.     slist *slow = head, *fast = head;    
    3.     while ( fast && fast->next )   
    4.     {  
    5.         slow = slow->next;  
    6.         fast = fast->next->next;  
    7.         if ( slow == fast ) break;  
    8.     }    
    9.     if (fast == NULL || fast->next == NULL)  
    10.         return NULL;  
    11.     slow = head;  
    12.     while (slow != fast)  
    13.     {  
    14.          slow = slow->next;  
    15.          fast = fast->next;  
    16.     }  
    17.     return slow;  

    亦可以用类似与hash表的方法,即设立一个数组,将链表结点中的值做数组下标,当赋值冲突时就是环的接入点

    1.  bool isloop(Llink p)
      {
       if(!p||!p->next)
        return true;
       int a[MAXSIZE],n=0;
       memset(a,0,sizeof(int)*MAXSIZE);
       p=p->next;
       while(p)
       {
        if(a[p->data]==-1)//存在环时,会发生冲突
        {
         cout<<"nLoop node: "<<p->data<<endl
          <<"nLen of node: "<<n<<endl;
         return true;
        }
        a[p->data]=-1;
        ++n;
        p=p->next;
       }
       return false;
      }
      Llink CreatlinkLoop()
    2. //创建一个有环的链表
      {
       Llink head=new Lnode;
       //head->data=0;
       head->next=NULL;
       Lelemtype e;
       Llink q=head;
       int N=0;
       cout<<"input elems:";
       while(cin>>e)
       {
        Llink p=new Lnode;
        ++N;
        p->data=e;
        p->next=q->next;
        q->next=p;
        q=p;
       }
       cin.clear();
       cin.sync();
       srand(time(0));
       q->next=Findnode(head,rand()%N);//随机产生环的接入点
       return head;
      }
      Llink Findnode(Llink head,int n)//找出链表中的第n个结点
      {
       if(n<=0)
        return head;
       Llink p=head->next;
       for(int i=1;p&&i<n;++i)
        p=p->next;
       return p;
      }

    附注

    问题2的证明如下:

    链表形状类似数字 6 。
    假设甩尾(在环外)长度为 a(结点个数),环内长度为 b 。
    则总长度(也是总结点数)为 a+b 。
    从头开始,0 base 编号。
    将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
    当 i<a 时,S(i)=i ;
    当 i≥a 时,S(i)=a+(i-a)%b 。

    分析追赶过程:
    两个指针分别前进,假定经过 x 步后,碰撞。则有:S(x)=S(2x)
    由环的周期性有:2x=tb+x 。得到 x=tb 。
    另,碰撞时,必须在环内,不可能在甩尾段,有 x>=a 。

    连接点为从起点走 a 步,即 S(a)。
    S(a) = S(tb+a) = S(x+a)。
    得到结论:从碰撞点 x 前进 a 步即为连接点。

    根据假设易知 S(a-1) 在甩尾段,S(a) 在环上,而 S(x+a) 必然在环上。所以可以发生碰撞。
    而,同为前进 a 步,同为连接点,所以必然发生碰撞。

    综上,从 x 点和从起点同步前进,第一个碰撞点就是连接点。

    /

    假设单链表的总长度为L,头结点到环入口的距离为a,环入口到快慢指针相遇的结点距离为x,环的长度为r,慢指针总共走了s步,则快指针走了2s步。另外,快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离),得到以下关系:
        s = a + x;
        2s = a + nr + x;
        =>a + x = nr;
        =>a = nr - x;
        由上式可知:若在头结点和相遇结点分别设一指针,同步(单步)前进,则最后一定相遇在环入口结点,搞掂!
    附图:

    带环的链表
    展开全文
  • 题目要求:给定一个单链表的头指针head,要求写一个函数判断个单链表是否是一个有环单链表。 单链表中的节点定义如下: struct listNode { int val; struct listNode *next; }; 方法1:首先定义一个map map,然后...
  • 判断一个单链表是否有环及环的链接点 转载▼ 给定一个单链表,只给出头指针h: 1、如何判断是否存在环? 2、如何知道环的长度? 3、如何找出环的连接点在哪里? 4、带环链表的长度是多少? ...
  • 1、遇到这问题,首先想到的是遍历链表,寻找是否有相同地址,借此判断链表中是否有环。 listnode_ptr current =head->next; while(current) { if(current==head) { printf("有环!\n"); return 0; } ...
  • 快慢指针查询,快指针每次跳两个,慢指针每次跳一个,如果两指针相等时,就证明有环 环的入口: 用两个指针,一个指向快慢指针相交点(这里就是慢指针走,慢指针在走快指针的一半就相当于快指针走的路了,还会到这个...
  • 题目:如何判断一个单链表是否有环?若有环,如何找出环的入口节点。 一、单链表是否有环 思路分析: 单链表有环,是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点,这样在链表的尾部形成一...
  • 主函数中没有出现具体的链表,主要看判断有无函数ExitLoop. 外函数的while循环条件的判定:如果fast指针指向NULL,if条件语句不成立,返回flag=0:不存在。 如果flag走到最后一个结点时,要是不给定一个条件,...
  • 最容易想到的办法就是遍历单链表,如果单链表有环的话那么会进入死循环,但是我们不知道单链表的长度,所以如果单链表长度很长,我们一直向下遍历,也无法分辨出是单链表还没遍历完还是进入了死循环。 所以这种解法...
  • 判断是否有环: 如果链表有环,那么在遍历时则会陷入死循环。 使用快慢指针 快指针移动2步,慢指针移动1步 如果走到某一步,快慢指针相遇,则说明有环 环入口点: 我们假设链表头部到环入口距离 len, 环入口...
  • 面试时只想到了最简单的遍历方法,每遍历一个节点,都保存节点,到新节点时,从保存的节点中查找是否存在地址相同的,存在就是有环的,否则无环。问我有没有别的方法时,就想不到了。 有环链表 看图更直观。 // ...
  • 声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为...题目:判断一个单链表是否有环,如果有环,求出环的入口节点。 ...
  • 判断一个单链表是否有环及环的链接点(转) 给定一个单链表,只给出头指针h: 1、如何判断是否存在环? 2、如何知道环的长度? 3、如何找出环的连接点在哪里? 4、带环链表的长度是多少? 解法: 1、对于...
  • 判断一个单链表是否有环及环的链接点(转) (2011-09-16 10:24:10) 转载▼   分类: 学习笔记 给定一个单链表,只给出头指针h: 1、如何判断是否存在环? 2、如何知道环的长度? 3、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,412
精华内容 564
关键字:

判断一个单链表是否有环