0141-环形链表

环形链表

方案一

---

只需要设两个指针，一个每次走一步的慢指针和一个每次走两步的快指针，如果链表里有环的话，两个指针最终肯定会相遇

借助单链表实现

C-源代码

---

#include <stdlib.h>
#include <stdbool.h>

#include "LinkList.h"

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

/**
 创建环
 
 @return 环
 */
struct ListNode *create_cycle_list()
{
    struct ListNode *node1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node1->val = 1;
    
    struct ListNode *node2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node2->val = 2;
    
    struct ListNode *node3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node3->val = 3;
    
    struct ListNode *node4 = (struct ListNode *)malloc(sizeof(struct ListNode));
    node4->val = 4;
    
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;
    
    return node1;
}

void test_0141(void)
{
    int arr[4] = { 1, 2, 3, 4 };
    struct ListNode *l1 = createNode(arr, sizeof(arr) / sizeof(arr[0]));
    
    struct ListNode *l2 = create_cycle_list();
    
    printf("========环形链表测试========\n");
    bool isCycle = hasCycle(l1);
    printf("是否存在环:1是，0不是=>%d\n",isCycle);
    
    bool isCycle1 = hasCycle(l2);
    printf("是否存在环:1是，0不是=>%d\n",isCycle1);
}

参考Grandyang