• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

141 循环链表(快速和慢速指针)


Recommended Posts

1. 环形链表

给你一个链表的头节点,判断链表中是否有环。

如果链表中有一个节点可以通过连续跟踪下一个指针再次到达,那么链表中就有一个环。为了表示给定链表中的环,求值系统内部使用整数pos来表示链表末尾连接到链表的位置(索引从0开始)。注意:pos不是作为参数传递的。只是为了识别链表的实际情况。

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

示例1:

circularlinkedlist.png

输入:head=[3,2,0,-4],pos=1

输出:真

说明:链表中有一个环,它的尾部与第二个节点相连。

示例2:

circularlinkedlist_test2.png

输入:head=[1,2],pos=0

输出:真

说明:链表中有一个环,它的尾部与第一个节点相连。

示例3:

circularlinkedlist_test3.png

Input: head=[1],pos=-1

输出:假

说明:链表中没有环。

提示:

链表中节点的数量范围是[0,104]

-105=Node.val=105

Pos为-1或链表中的有效索引。

1 /**

2 *单链表的定义。

3 *结构列表节点{

4 * int val

5 * ListNode * next

6 * ListNode(int x) : val(x),next(NULL) {}

7 * };

8 */

9级解决方案{

10 public:

11 bool hasCycle(ListNode *head) {

12 if(head==nullptr | | head-next==nullptr){

13返回假;

14 }

15 ListNode * slow=head

16 ListNode * fast=head

17 while(慢!=nullptr快!=nullptr fast-next!=nullptr) {

18慢=慢-下;

19快=快-下-下;

20 if (slow==fast) {

21返回true

22 }

23 }

24返回假;

25 }

26 };

Link to comment
Share on other sites