题目: 142. Linked List Cycle II

描述:

 * Given a linked list, return the node where the cycle begins. 
 * If there is no cycle, return null.
 * To represent a cycle in the given linked list, 
 * we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. 
 * If pos is -1, then there is no cycle in the linked list.
 * Note: Do not modify the linked list.
 *
 * Example 1:
 * 
 *     3 -> 2 -> 0 -> -4  
 *          ↖        ↙  
 *            ← ← ← ←
 *
 * Input: head = [3,2,0,-4], pos = 1
 * Output: tail connects to node index 1
 * Explanation: There is a cycle in the linked list, where tail connects to the second node.
 * 
 * Example 2:
 *
 *          1 - > 2   
 *          ↖   ↙  
 *            ←
 * Input: head = [1,2], pos = 0
 * Output: tail connects to node index 0
 * Explanation: There is a cycle in the linked list, where tail connects to the first node.
 * 
 * Example 3:
 *
 *          1
 * 
 * Input: head = [1], pos = -1
 * Output: no cycle
 * Explanation: There is no cycle in the linked list.
 * 

演示：

/*
 *              l    f
 *         1 -> 2 -> 3 -> 4 -> 5 
 *                   ↖       ↙  
 *                     ← 6 ←
 *
 *                   l         f
 *         1 -> 2 -> 3 -> 4 -> 5 
 *                   ↖       ↙  
 *                     ← 6 ←
 *
 *                   f    l
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖       ↙  
 *                     ← 6 ←
 *
 *                             lf         Found
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖       ↙  
 *                     ← 6 ←
 *
 *         |     a   |    b    |
 *         l                   f
 *         1 -> 2 -> 3 -> 4 -> 5 
 *                   ↖       ↙  
 *                     ← 6 ←
 *                    |  c  |  
 *                    
 *
 *         |     a   |    b    |
 *              l              
 *         1 -> 2 -> 3 -> 4 -> 5 
 *                   ↖       ↙  
 *                     ← 6 ←
 *                       f
 *                    |  c  |  
 *
 *         |     a   |    b    |
 *                  lf         
 *         1 -> 2 -> 3 -> 4 -> 5 
 *                   ↖       ↙  
 *                     ← 6 ←
 *                    |  c  |  
 *
 * * * * * * * * * * * * *
 *              l    f          
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙  
 *                     ← ← ← ←
 *
 *                   l         f
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙  
 *                     ← ← ← ←
 *
 *                        lf         
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙  
 *                     ← ← ← ←
 *
 *                        lf             Found
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙  
 *                     ← ← ← ←
 *
 *         a             b                    
 *                        lf             Found
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙     c
 *                     ← ← ← ←
 *
 *         | a       |    b    |
 *         l              f              
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙     
 *                     ← ← ← ←
 *                   |   c     |
 *
 *              l              f
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙     c
 *                     ← ← ← ←
 *
 *                   lf        
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙     c
 *                     ← ← ← ←
 *
 *         |    a    |    b     |
 *         1 -> 2 -> 3 -> 4 -> 5
 *                   ↖        ↙     c
 *                     ← ← ← ←
 *
 * * * * * * * * * * * * *
 *      2 * sum = a + m*(b+c) + b
 *      1 * sum = a + n*(b+c) + b
 *
 *      2a +     2n(b+c) + 2b = a + m*(b+c) +b
 *       a + (2n-m)(b+c) +  b = 0
 *           (m-2n)(b+c)      = a + b
 *           (m-2n)(b+c)      = a + b -c + c
 *         (1+m-2n)(b+c)      = a + b -c + c
 *
 *           x     (b+c)      = a + b
 *           a                = x * (b+c) - b
 *           a                = (x-1) * (b+c) + b + c - b
 *           a                = (x-1) * (b+c) + c 
 *           a                = c
 *
 *         
 */

代码:

#include <iostream>
#include <vector>

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;
        while(fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
            {
                std::cout << "Exist:" << slow->val << ", " << fast->val << std::endl;
                fast = head;
                while (fast != slow)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                std::cout << "endwhile:" << slow->val << ", " << fast->val << std::endl;
                std::cout << fast << std::endl;
                return slow; 
            }
        }
        return NULL;
    }

    std::vector<int> printList(ListNode* head) 
    {
        std::vector<int> ret ; // = new ArrayList<>();
        ListNode *listNode = head;
        if (head)
        {
            std::cout << "head" << listNode->val << std::endl;
        }
        else
        {
            std::cout << "null" << std::endl;
        }
        while (listNode != nullptr) // && listNode->next != nullptr) 
        {
            std::cout << listNode->val << " " ; // << std::endl;
            ret.push_back(listNode->val);
            listNode = listNode->next;
        }
        std::cout << std::endl;
        return ret;
    }
};

int main()
{
    /*
     *
     *         1 -> 2 -> 3 -> 4 -> 5
     *              ↖            ↙  
     *                ← ← ← ← ← ←
     *
     *
     */
    struct ListNode * p1 = new ListNode(1);
    struct ListNode * p2 = new ListNode(2);
    struct ListNode * p3 = new ListNode(3);
    struct ListNode * p4 = new ListNode(4);
    struct ListNode * p5 = new ListNode(5);
    
    struct ListNode * q1 = new ListNode(6);

    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = p5;

    p5->next = p2;

    Solution a;

    std::cout << "before detect:";// << detect->val;
    std::cout << p2 << std::endl;
    ListNode * detect = a.detectCycle(p1);
    std::cout << "detect:" << std::endl;
    if (detect)
    {
        std::cout << detect->val;
    }
    else
    {
        std::cout << "NULL";
    }
    std::cout << "Q1:" << std::endl;
    detect = a.detectCycle(q1);
    if (detect != NULL)
    {
        std::cout << detect->val;
    }
    else
    {
        std::cout << "NULL";
    }
    return 0;
}