首页 > 一道数据结构算法题

一道数据结构算法题

现有一个链表，证明如果存在环，则：使用两个指针同时前进但步长不一样，则能够在有限步之后能够相逢。



题目的意思是我归纳出来的，我的解题思路是这样的：



能够相下逢的意思是：

在走了x步以后，x×S1 和 x×S2 对N同余，其中S1、S2为两个指针的步长，N为环的长度。



(x*s1) %N = (x*s2) %N

等价于：

x*s1 - a*N = x*s2 - b*N

=> x = ( (a - b)*N ) / ( s1 - s2 )



a, b 为指针所走的圈数。a 和b之间的关系于s1,s2有关。

a/b = s1 / s2

这样，上式可改写为：

x = ( a*(1 - s2/s1)*N ) / (s1 - s2)

转载于:https://www.cnblogs.com/froster/archive/2005/12/28/306525.html

更多相关：

  • C/C++：*(p++)慎用！！！！！

    　　各位代码界的大佬大家好，今天跟大家分享一个在C/C++中常用，但是很危险的一串代码——*(p++) 　　为什么说这一行代码比较危险呢，因为对于C/C++来说，成也指针，败也指针。C/C++中指针便于我们操作一块连续的内存空间中内容，但是同时我们也要承担一些风险，比如：内存泄漏，野指针，只想垃圾数据等等。今天我们要说的就是指向垃圾数...

  • Chapter12：动态内存

    智能指针——shared_ptr为了更容易地使用动态内存，新的标准提供了智能指针来管理动态对象。智能指针的行为类似常规指针，重要的区别是它负责自动释放指向的对象。   智能指针的使用方式与普通指针类似。解引用一个智能指针返回它指向的对象。 1 if (p1 && p1->empty())   最安全的分配和使用动态内存的方法是调用...

  • 指针的各式定义

    1，一个整形数：  int a; 2，一个指向整形数的指针： int *a; 3，一个指向指针的指针，它指向的指针指向一个整形数：  int **a; 4，一个有10个整形数的数组： int a[10]; 5，一个有10个指针的数组，每个指针指向一个整形数： int *a[10]; 6，一个指向有10个整形数的数组的指针：  int...

  • 【数据结构】某些难理解点

    1 typedef char ListData; 2 //表示以后可以用ListData来代替char类型 3 4 typedef struct node{ //此处node，只在结构体中出现和使用 5 ListData data; 6 struct node *link; 7 }List...

  • 备忘：C++基础 -- 数据类型的学习总结

    常用的几种数据类型： 类型标识符 说明 字节 值的范围   int 整型 4 –2,147,483,648 到 2,147,483,647 VC++中为long int类 short 短整型 2 –32,768 到 32,767   long 长整型 4 –2,147,483,648 到 2,147,4...

©2024 11GX.COM