leetCode-0141_环形链表

Posted on | In |

题目描述

英文题目

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

中文题目

给定一个链表，判断链表中是否有环。

进阶：
你能否不使用额外空间解决此题？

解决方法

方法一
  • 描述

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

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 创建环
 
 @return 环
 */
struct ListNode *create_cycle_list()
{
    SingleLinkListNode *node1 = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    node1->val = 1;
    
    SingleLinkListNode *node2 = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    node2->val = 2;
    
    SingleLinkListNode *node3 = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    node3->val = 3;
    
    SingleLinkListNode *node4 = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    node4->val = 4;
    
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;
    
    return node1;
}


/**
 环形链表
 
 @param head 不带头结点
 @return 是否存在环
 */
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 (slow == fast) {
            return true;
        }
    }
    return false;
}

/**
 环形链表测试
 */
void hasCycle_test()
{
    SingleLinkListNode *head = single_link_list_create();
    single_link_list_insert_tail(head, 1);
    single_link_list_insert_tail(head, 2);
    single_link_list_insert_tail(head, 3);
    single_link_list_insert_tail(head, 4);
    
    printf("========环形链表测试========\n");
    bool isCycle = hasCycle(head->next);
    printf("是否存在环:1是，0不是=>%d\n",isCycle);
    
    SingleLinkListNode *cycleHead = create_cycle_list();
    bool isCycle1 = hasCycle(cycleHead);
    printf("是否存在环:1是，0不是=>%d\n",isCycle1);
}

题目来源

Linked List Cycle

环形链表

线性表相关代码

数据结构-线性表