精华内容
下载资源
问答
  • 判断链表有环

    2020-04-18 16:28:31
    //如何判断链表有环? function Node(ele){ this.element = ele this.next = null } //首先创建带环链表 var lian = { head: null } //添加结点 function append(lian, el...
    //如何判断链表有环?
    
         function Node(ele){
           this.element = ele
           this.next = null
         }
          //首先创建带环链表
          var lian = {
            head: null
          }
          //添加结点
         function append(lian, ele){
           var node = new Node(ele)
           var current
          if(lian.head===null){
            lian.head = node
          }else{
            current = lian.head
            while(current.next){
              current = current.next
            }
            current.next = node
          }
         }
         //查询指定节点
         function search(lian, ele){
          var current = lian.head
          while(current){
            if(current.element === ele){
              return current
            }
            current = current.next
          }
          return '没有'
         }
    
         append(lian, 1)
         append(lian, 2)
         //使lian为带环的链表
         search(lian,2).next = search(lian,1)
         
         function judge(lian){
           //采用遍历链表添加标识位的方式,每经过一个结点就为这个节点添加visited标志位表示已经过
           //那么一旦循环到visited=1的节点就说明这个节点已经被遍历过了
            var tempLian = Object.assign(lian)
            var current = tempLian.head
            current.visited = 1
            while(current.next){
              current = current.next
              if(current.visited === 1){ //表示该节点已经浏览过了 说明有环
                return true 
              }else{
                current.visited = 1
              }
            }
            
            return false
         }
    
         console.log(judge(lian)) 
         //当注释掉search(lian,2).next = search(lian,1)时返回false
         //当没有注释掉search(lian,2).next = search(lian,1)时返回true
    
    展开全文
  • 最近看了程序员小灰的一篇文章漫画算法:如何判断链表有环?, 问题描述如下:有一个单向链表,链表当中有可能出现“环”,就像下图这样。如何用程序判断出这个链表是有环链表?如下图所示一个带环的单向链表.文章中的...

    902a4c4abe1840caba6a3d426c1eb006.png

    最近看了程序员小灰的一篇文章漫画算法:如何判断链表有环?, 问题描述如下:

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

    如下图所示一个带环的单向链表.

    f538bed01a6ed7eb3da6d5df4991185e.png

    文章中的方法三给出了简洁的算法:

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

    首先这个算法是正确的,但是我更期望是从数学上使用关系式对这个追及问题进行量化描述。我们把这些个链表看成一条路线, 每个结点为路线上的刻度,它们间的间距相同。上图链表的类比模型如下:

    31d9a5c7212ae93cb7536c31d1a202cd.png
    (图中起点O到入口点E的长度|OE|为6, 环长为6)

    更一般地行走路线如下:

    81fc5c56d87e0514ba1a1ed6752cfc72.png

    上图中, O为起点, 入口点为E; 初始时, 指针Slow和Fast均在O点,然后指针Slow以每次步长为1前进, 指针Fast以步长为2前进, 它们最终在环形中的第一次相遇点为M。

    起点O到入口E的长度为|OE|, 圆环的长度为L; Fast和Slow相遇时, Fast在圆环上走过的长度为S_fast(备注: 它可能在里面走了好几圈), Slow在圆环上走过的长度为S_slow。

    有如下等式成立:

    a. |OE| + S_fast = 2 * (|OE| + S_slow) (备注: Fast从O开始走的总长是Slow的2倍)

    b. S_slow = S_fast - N * L (且整数N>=1) (备注:Fast比Slow先到环上,然后多跑了N圈)

    继续变换等式 =>

    a. S_fast = |OE| + 2 * S_slow

    b. S_fast = S_slow + N * L

    所以有:

    |OE| + 2 * S_slow = S_slow + N * L

    最终为 =>

    S_slow = N * L - |OE| (关系式0)

    观察关系式0,因为S_slow是大于等于0的, 那么N有很多取值(只要N*L-|OE|的结果大于等于0就行),肯定存在这种情况N=x时,x*L -|OE|小于0,(x+1)*L-|OE|大于等于0,所以N=x+1时就是他们第一次相遇时,且此时 S_slow是小于或等于L的,也就是说slow指针最多在环上跑一圈。看下图数轴:

    a62f57c260a9bec67d1758d11e74d906.png

    考虑如下Corner Case:

    1. |OE| = 0, 那么N为1即可, 则有 S_slow = L, S_fast = 2 * L; 也就是该链表就是个环形链表;
    2. L = 1, 就是最后一个节点指向它自己。如下图示:

    08459d0c55f1d0efd7517ab5e458c519.png

    此时, S_slow = 0即可, 也就是说, Fast指针在环上跑了|OE|圈,直到Slow到达入口点E。

    由上可知,这个算法时间复杂度为O(N),空间复杂度为O(1)。

    问题延伸

    Q: 在一个有环链表中,如何找出链表的入环点?

    A: 由关系式0可知 S_slow + |OE| = N * L,也就是说相遇点M处, Slow指针继续前行|OE|距离会停在入口点E(别忘了Slow是从E处进入圆环的, 此时Slow会多走几圈,但是最终会停在入口点E) ,而从起点O到E的距离也是|OE|,所以我们将 Slow指针从M处继续走|OE|长度,Fast指针从O点以每次1个步长走|OE|长度,他们会相遇在E点。这样就得到了入口点E。

    源码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <assert.h>
    
    
    #define ARRAY_COUNT(a)	(sizeof(a)/sizeof(a[0]))
    #define INDEX_NONE		(-1)
    
    struct FLinkNode
    {
    	FLinkNode()
    		: mValue(0)
    		, mNext(-1)
    	{}
    
    	int		mValue;
    	int		mNext;
    };
    
    struct FCheckResult
    {
    	FCheckResult()
    		: mHasCircle(false)
    		, mEntryPtr(INDEX_NONE)
    	{}
    
    	bool	mHasCircle;
    	int		mEntryPtr;
    };
    
    FCheckResult CheckCircleLinkAndFindEntry(const FLinkNode *InArray)
    {
    	assert(!!InArray);
    
    	FCheckResult Result;
    	Result.mHasCircle = false;
    	Result.mEntryPtr = INDEX_NONE;
    
    	// walk through link
    	int FastPtr = 0, SlowPtr = 0;
    	while (FastPtr != INDEX_NONE && SlowPtr != INDEX_NONE)
    	{
    		// one step
    		SlowPtr = InArray[SlowPtr].mNext;
    		// two steps
    		FastPtr = InArray[FastPtr].mNext;
    		if (FastPtr == INDEX_NONE)
    		{
    			break;
    		}
    		FastPtr = InArray[FastPtr].mNext;
    		if (FastPtr == INDEX_NONE)
    		{
    			break;
    		}
    
    		if (SlowPtr == FastPtr)
    		{
    			// it is a circle link, then find the entry node.
    			FastPtr = 0;
    			while (FastPtr != SlowPtr) // 注意:该链表整就是个环形链表, 所以要先判断 FastPtr != SlowPtr
    			{
    				assert(FastPtr != INDEX_NONE && SlowPtr != INDEX_NONE);
    
    				FastPtr = InArray[FastPtr].mNext;
    				SlowPtr = InArray[SlowPtr].mNext;
    			};
    
    			Result.mHasCircle = true;
    			Result.mEntryPtr = FastPtr;
    			
    			break;
    		}
    	} // end while
    
    	return Result;
    }
    
    // return entry pointer
    int InitializeLink(FLinkNode *InArray, const int InCount)
    {
    	assert(!!InArray);
    
    	for (int k = 0; k < InCount; k++)
    	{
    		InArray[k].mValue = k;
    		InArray[k].mNext = k + 1;
    	}
    
    	int LastNext = rand() % InCount;
    	InArray[InCount - 1].mNext = LastNext;
    
    	return LastNext;
    }
    
    int main()
    {
    	// 为了方便测试,使用数组来表示链表.
    	FLinkNode LinkArray[1024];
    
    	srand(time(0));
    	for (int i = 0; i < 100; i++)
    	{
    		int EntryPointer = InitializeLink(LinkArray, ARRAY_COUNT(LinkArray));
    
    		FCheckResult Result = CheckCircleLinkAndFindEntry(LinkArray);
    
    		assert(Result.mHasCircle == true);
    		printf("CASE %d: EntryPointer=%d,  TEST Result: Has Circle=%s, Entry Pointer=%dn", i, EntryPointer, Result.mHasCircle ? "true" : "false", Result.mEntryPtr);
    	}
    
    	// Corner Case 0
    	{
    		int EntryPointer = InitializeLink(LinkArray, ARRAY_COUNT(LinkArray));
    		EntryPointer = 0;
    		LinkArray[ARRAY_COUNT(LinkArray) - 1].mNext = EntryPointer;
    		FCheckResult Result = CheckCircleLinkAndFindEntry(LinkArray);
    		assert(Result.mHasCircle == true);
    		printf("CORNER CASE : EntryPointer=%d,  TEST Result: Has Circle=%s, Entry Pointer=%dn", EntryPointer, Result.mHasCircle ? "true" : "false", Result.mEntryPtr);
    	}
    
    	// Corner Case 1
    	{
    		int EntryPointer = InitializeLink(LinkArray, ARRAY_COUNT(LinkArray));
    		EntryPointer = ARRAY_COUNT(LinkArray) - 1;
    		LinkArray[ARRAY_COUNT(LinkArray) - 1].mNext = EntryPointer;
    		FCheckResult Result = CheckCircleLinkAndFindEntry(LinkArray);
    		assert(Result.mHasCircle == true);
    		printf("CORNER CASE: EntryPointer=%d,  TEST Result: Has Circle=%s, Entry Pointer=%dn", EntryPointer, Result.mHasCircle ? "true" : "false", Result.mEntryPtr);
    	}
    
    	// Corner Case 2
    	{
    		int EntryPointer = InitializeLink(LinkArray, ARRAY_COUNT(LinkArray));
    		EntryPointer = INDEX_NONE;
    		LinkArray[ARRAY_COUNT(LinkArray) - 1].mNext = EntryPointer;
    		FCheckResult Result = CheckCircleLinkAndFindEntry(LinkArray);
    		assert(Result.mHasCircle == false);
    		printf("CORNER CASE: EntryPointer=%d,  TEST Result: Has Circle=%s, Entry Pointer=%dn", EntryPointer, Result.mHasCircle ? "true" : "false", Result.mEntryPtr);
    	}
    
    	system("pause");
        return 0;
    }
    
    展开全文
  • 如何判断链表有环

    2020-12-12 17:05:50
    如何判断链表有环 通过快慢指针来实现,快指针每次前进两个元素,慢指针每次前进一个元素,如果快慢指针相遇,则表示链表有环。 * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x),...

    如何判断链表有环

    通过快慢指针来实现,快指针每次前进两个元素,慢指针每次前进一个元素,如果快慢指针相遇,则表示链表有环。

     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     
        bool hasCycle(ListNode *head) {
            if (head == nullptr) return false;
            ListNode* flag = head;
            ListNode* fast = head;
            ListNode* slow = head;
            while(fast->next != nullptr && fast->next->next != nullptr) {
                fast = fast->next->next;
                slow = slow->next;
                if (fast == slow) return true;
            }
            return false;
        }
    
    展开全文
  • 如何判断链表有环摘自漫画算法:题目:有一个单向链表,链表中有可能出现“环”,就像下图这样,那么如何用程序来判断该链表是否为有环链表呢?方法1首先从头节点开始,以此遍历单链表中的每一个节点。每遍历一个新...

    如何判断链表有环

    摘自漫画算法:

    题目:有一个单向链表,链表中有可能出现“环”,就像下图这样,那么如何用程序来判断该链表是否为有环链表呢?

    9434033bbead9a16eab79d0b08b4f2c8.png

    方法1

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

    5ef3eb18f3f682a4e1e10382c0db06dc.png

    就像图中这样,当遍历链表节点7时,从头访问节点5和3,发现已遍历的节点中并不存在节点7,则继续往下遍历。

    当第2次遍历到节点2时,从头访问曾经遍历过的节点,发现已经遍历过节点2,说明链表有环。

    假设链表的节点数量为n,则该解法的时间复杂度为O(n²)。由于并没有创建额外的存储空间,所以空间复杂度为O(1)。

    方法2

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

    b33719d2d0d563eb00115b3981030f58.png

    遍历过5、3、7、2、6、8、1。

    a1e946893e2cca4088c41b804f81554c.png

    当再次遍历节点2时,查找HashSet,发现节点已存在。

    7c503c50f660cf4160f22da380e324e2.png

    由此可知,链表有环。

    这个方法在流程上和方法1类似,本质的区别是使用了HashSet作为额外的缓存。假设链表的节点数量为n,则该解法的时间复杂度是O(n)。由于使用了额外的存储空间,所以算法的空间复杂度同样是O(n)。

    方法3

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

    步骤如下:

    1、p1和p2都指向节点5

    d4e799b51f6ec87136abeb59d0bf50eb.png

    2、p1指向节点3,p2指向节点7

    30f3a254fb3fd5e4634f08da2a7b0358.png

    3、p1指向节点7,p2指向节点6

    dade999accacbf5a72ce013d699d01a0.png

    4、p1指向节点2,p2指向节点1

    2994967722b2f47d7a1fd45761b46ad4.png

    5、p1指向节点6,p2也指向节点6,p1和p2所指相同,说明链表有环

    a4b2a36f69d1d3ef96d60ae746bba726.png

    学过小学奥数的读者,一定听说过数学上的追及问题。此方法就类似于一个追及问题。

    在一个环形跑道上,两个运动员从同一起点炮,一个运动员速度快,另一个运动员速度慢。当两人跑了一段时间后,速度快的运动员必然会再次追上并超过速度慢的运动员,原因很简单,因为跑道是环形的。

    假设链表的节点数量为n,则该算法的时间复杂度为O(n)。除两个指针外,没有使用任何额外的存储空间,所以空间复杂度是O(1)。

    代码实现:

    /**

    * Create By ZhangBiao

    * 2020/6/4

    */

    public class LinkedList {

    /**

    * 链表节点

    */

    private static class Node {

    int data;

    Node next;

    public Node(int data) {

    this.data = data;

    }

    }

    /**

    * 判断链表是否有环

    *

    * @param head 链表头节点

    * @return

    */

    public static boolean isCycle(Node head) {

    Node p1 = head;

    Node p2 = head;

    while (p2 != null && p2.next != null) {

    p1 = p1.next;

    p2 = p2.next.next;

    if (p1 == p2) {

    return true;

    }

    }

    return false;

    }

    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);

    node1.next = node2;

    node2.next = node3;

    node3.next = node4;

    node4.next = node5;

    node5.next = node2;

    System.out.println(isCycle(node1));

    }

    }

    问题扩展

    1、如果链表有环,如何求出环的长度?

    e2aa62604cf1df8051daf7f6cf1fa73d.png

    解法如下:

    当两个指针首次相遇,证明链表有环的时候,让两个指针从相遇点继续循环前进,并统计前进的循环次数,知道两个指针第2次相遇。此时,统计出来的前进次数就是环长。

    因此指针p1每次走1步,指针p2每次走2步,两者的速度差是1步。当两个指针再次相遇时,p2比p1多走了整整1圈。因此,环长 = 每一次速度差 * 前进次数 = 前进次数。

    展开全文
  • 20200612-判断链表有环

    2021-01-16 10:14:30
    1.1 判断链表有环 Linked List Cycle Linked List Cycle II 这2道题都和判断链表是否有环相关,看下给的例子 Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list,...
  • 文章目录如何判断链表有环解法一解法二解法三解法评估最后 如何判断链表有环 给一个单向链表,使用程序来判断链表中是否存在环结构。 private static class Node { int data; Node next; Node(int data) { this...
  • 【算法】如何判断链表有环
  • 如何判断链表有环

    2020-05-19 21:39:45
    一个单向链表,链表中可能出现 “环”,就像下图这样。...如果相同,则判断链表有环,如果不同,则继续下一循环。 假设链表的节点数量是n,则该算法的时间复杂度是O(n)。除两个结点外,没有使用任何.
  • 如何判断链表有环 设置快慢指针,两个指针都从头节点开始,快指针一次走两步,慢指针一次走一步,如果快慢指针相遇则链表有环。 伪代码:node *fast=head; node *slow=head; while(fast!=NULL&&fast->...
  • java实现判断链表有环

    2019-08-22 17:34:39
    判断链表有环 使用两个指针left和right指向起点,每次left指针向后走一步,right指针向后走两步,上图是两个指针走一次后的结果。直到left和right指针再次指向同一个节点,说明该链表是有环链表。 private ...
  • 1、判断链表有环,找到入环口 方法与思路我都写在注释里 /* 思路:判断是否有环,快指针走两步,慢指针走一步 如果有环,能在环内相遇(是指指的节点相同,即地址一样) 判断入环口,在前面求出的相遇点用慢指针...
  • 如何判断链表有环? 1,什么是有环链表? 一个有环的链表 :eg. A->B->C->D->B->C->D 如图: 2,如何判断链表有环? 第一种方法:遍历:出现两个相同节点则证明出现环,利用HashSet存放已遍历...
  • package demo6;import java.util.HashMap;.../*** 判断链表是否有环的方法* @author mengfeiyang**/public class LinkLoop {public static boolean hasLoop(Node n){//定义两个指针tmp1,tmp2Node tmp1 = ...
  • 经典面试题 如何判断链表有环 参考链接 http://blog.csdn.net/thefutureisour/article/details/8174313 http://blog.csdn.net/liuxialong/article/details/6555850 题目背景 给定一个单链表,只给出头指针\(h\),...
  • 判断链表有环&求循环列表环长&求循环列表入环点 关于更多的链表实现可以从下方直通车达到: 单向链表 双向链表 循环链表 本篇希望着重介绍的是结合数学中的追及问题与循环列表来达到判断列表有环和求环长 ...
  • public class 如何判断链表有环 { /** * @param args */ public static boolean isCycle(Node head) { Node p1 = head; Node p2 = head; while (p2 != null && p2.next != null) { p1 = p1....
  • 代码:判断链表有环(python) 141. 环形链表 class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if not head: return Fals...
  • 面试官:你来说说怎么判断链表有环? AXin:什…什么是链表有环? 面试官:环都不知奥?喝乌俺~huan,环,就是下面这个样子,只会出现情况1和情况2,不会出现情况3这种。而且环有且只有一个,一定包含最后一个节点。...
  • 判断链表有环及其扩展问题 单链表里可能有环,如何判断有环? 环大小是多少?能否找到环的第一个节点? (1)判断有环 设置两个指针,快慢指针,p1,p2,p2一次走两步,p1一次走一步。如果p2走的过程中到达表尾,则...
  • 给定一个链表,判断链表中是否有环。 主要是运用快慢指针 直接贴c++代码: bool hasCycle(ListNode *head) { if (head == NULL || head->next == NULL) return false; //快慢指针 ListNode *fast = head->...
  • 如何判断单链表有环,并找出环的入口? 时间O(n),空间O(1)。...对于如何判断链表有环,可以从起点发出两个指针,一个一次一步,另一个一次两步,如果两个指针相遇,那么这个单链表就有环。 设绿...

空空如也

空空如也

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

判断链表有环