nba买球[LeedCode OJ]#142 Linked List Cycle II

作者:计算机教程

[LeedCode OJ]#141 Linked List Cycle

 

 

题意:

给定一个链表,判断这个链表是否有环

 

思路:

设定快慢指针,快指针一次走两步,慢指针一次走一步,如果快指针到达NULL就代表无环,一旦快指针与慢指针相等那么就代表有环

 

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        if(head==NULL)
            return false;
        ListNode *fast,*slow;
        fast = slow = head->next;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow)
                return true;
        }
        return false;
    }
};

 

 

http://www.bkjia.com/cjjc/1051721.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1051721.htmlTechArticle[LeedCode OJ]#141 Linked List Cycle 题意: 给定一个链表,判断这个链表是否有环 思路: 设定快慢指针,快指针一次走两步,慢指针一次走一步,...

[LeedCode OJ]#142 Linked List Cycle II

 

nba买球, 

题意:

对于一个链表,判断其是否有环,有环则返回环的起始位置。

 

思路:

通过141题,我们知道可以通过快慢指针来判断是否有环,现在我们假设两个指针相遇在z点,如图

nba买球 1

那么我们可以知道fast指针走过a b c b

slow指针走过a b

那么2*(a b) = a b c b

所以a = c

那么此时让slow回到起点,fast依然停在z,两个同时开始走,一次走一步

那么它们最终会相遇在y点,正是环的起始点

 

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
 public:
  ListNode *detectCycle(ListNode *head)
  {
   ListNode *slow = head;
   ListNode *fast = head;
   do
   {
    if(!slow||!fast)
     return nullptr;
    slow = slow->next;
    fast = fast->next;
    if(fast)
     fast = fast->next;
    else
     return nullptr;
   }
   while(slow!=fast);

   slow = head;
   while(slow!=fast)
   {
    slow = slow->next;
    fast = fast->next;
   }
   return slow;
  }
};

 

 

 

http://www.bkjia.com/cjjc/1052688.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1052688.htmlTechArticle[LeedCode OJ]#142 Linked List Cycle II 题意: 对于一个链表,判断其是否有环,有环则返回环的起始位置。 思路: 通过141题,我们知道可以通过快...

本文由nba买球发布,转载请注明来源

关键词: