力扣 141.环形链表和142.环形链表2

简介: 力扣 141.环形链表和142.环形链表2

1.环形链表Ⅰ解题思路

利用快慢指针,快指针一次走两个,慢指针一次走一个,如果出现了快指针为空或者快指针的next为空的现象则说明不带环,但如果带环,那么快指针就一定能够追上慢指针,原理如下

2.环形链表Ⅰ代码实现

bool hasCycle(struct ListNode *head)
 {  if(head==NULL)
    return false;
     if(head->next==NULL)
     return false;
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast)
    {   if(fast->next==NULL)
        return false;
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow&&fast!=NULL)
        return true;
    }
return false;
}

3.环形链表Ⅱ解题思路

首先利用环形链表Ⅰ的思路可以求出快慢指针相遇时指针的位置则可设此位置距离循环开始的位置距离为X,设从开头到循环点的距离为L,环的长度为C,则慢指针走的路程就为L+X,而且快指针走的距离就为L+n*C+X,则由数学公式推理可得:一个指针从相遇点走,另一个指针从开头走,则他们会在循环入口点相遇,由此特性就可得出循坏的开始点.

4.环形链表Ⅱ代码实现

struct ListNode *detectCycle(struct ListNode *head) 
{   
     if(head==NULL)
    return NULL;
     if(head->next==NULL)
     return NULL;
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast)
    {   if(fast->next==NULL)
        return NULL;
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow&&fast!=NULL)
        break;
    }
    if(fast==NULL)
    return NULL;
  struct ListNode *p=head;
    while(p!=fast)
    {
fast=fast->next;
p=p->next;
    }
return fast;
}

结尾:今天的分享到此结束,喜欢的朋友如果感觉有帮助可以点赞三连支持,咱们共同进步!

目录
相关文章
|
1天前
【数据结构OJ题】环形链表
力扣题目——环形链表
12 3
【数据结构OJ题】环形链表
|
1天前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
9 1
【数据结构OJ题】环形链表II
|
19天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
19天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
19天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
19天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
31 1