个人技术分享

 一、环形链表I 

题目 

思路 

该题使用快慢指针 slow、 fast 

slow 走一步 ，fast 走两步 

当fast 走到空  或者 fast的下一个结点为空， 则无环

fast若追上slow ， 则有环

结论证明

该思路默认了 ：

若存在环形链表 ， 无论两个指针的步差是多少，快指针 一定可以追上 慢指针

下面我们对该结论用数学归纳法进行证明:从简单的情况推广到更普遍的情况

代码

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

二、环形链表II 

题目

相比上一题目 ，该题需要我们求入口点。

思路一

结论： 一个指针从链表头节点走 另一个指针从相遇点走  两个指针会在 入口点相遇

结论证明

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow, *fast;
    slow = fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        // 找相遇点
        if (slow == fast) {
            struct ListNode* meet = slow;
            while (head != meet) {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}