0141-环形链表

环形链表

解题方法

1. 给定一个时间，无限循环，判断是否存在空
2. 利用Set(集合），遍历过程判判断此节点是否在Set中，不在的话，就把此节点加到Set中
3. 利用快慢指针

方案一

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

借助单链表实现

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);
}

Swift实现

public class ListNode {
    
    public var key: Int?
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        
        self.val = val
        self.next = nil
    }
}

extension ListNode: Equatable {
    
    public static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        
        if let lKey = lhs.key,
            let rKey = rhs.key,
            lKey == rKey {
            
            return true
        }
        
        return false
    }
}

func hasCycle(_ head: ListNode?) -> Bool {
        
        var fast: ListNode? = head
        var slow: ListNode? = head
        while fast != nil && fast?.next != nil {
            
            fast = fast?.next?.next
            slow = slow?.next
            
            if fast == slow {
                
                return true
            }
        }
        return false
    }

参考Grandyang