admin管理员组

文章数量:1794759

【oj题】环形链表

一. OJ链接： 环形链表

【思路】 快慢指针

即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

代码语言：javascript代码运行次数：0运行复制
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
{
    ListNode* fast , *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        return true;
    }   
    return false;
}

【扩展问题】 为什么快指针每次走两步，慢指针走一步可以解决问题？

如果链表不带环，两个指针一定不会相遇，因为fast = 2slow 假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。 当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度-1。 此时，两个指针每移动 一次，之间的距离就缩小一步。因此，在慢指针走到一圈之前， 快指针肯定是可以追上慢指针的，即相遇。

【扩展问题】快指针一次走3步，走4步，...n步行吗？

假设快指针一次走3步，慢指针一次走1步

同理可证，快指针走4,5……也行

二. OJ链接：环形链表||

相遇时，slow指针与fast指针走的路程

head指针走L步，meet指针走C-N步，head指针和meet指针相遇，此时就是环的第一个节点

代码语言：javascript代码运行次数：0运行复制
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow) {
            struct ListNode *ptr = head, *meet = slow;
            while (ptr != meet) {
                ptr = ptr->next;
                meet = meet->next;
            }
            return ptr;
        }
    }
    return NULL;
}

一键三连~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-23，如有侵权请联系 cloudcommunity@tencent 删除指针intreturnstruct链表

本文标签： oj题环形链表

版权声明：本文标题：【oj题】环形链表 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754645703a1704724.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。