02-判断一个链表是否是环形链表：用快慢指针来实现

题目思路：用快慢指针的思想：快指针走两步，慢指针只走一步。如果这个链表是一个环，那么快指针和慢指针总会相遇的。-快慢指针的原理：假设快慢指针之间相差n步，慢指针先走一步，那么快慢指针相差n+1步然后快指针走两步，那么快慢指针相差n+1-2 = n-1步；也就是说，每走一次，快慢指针的距离就减少一次；那么走到n次的时候，快慢指针的相差就为0.ios代码实现（1）创建一个链表的类，如下：@inter

一人前行

137人浏览 · 2020-05-11 22:45:16

一人前行 · 2020-05-11 22:45:16 发布

题目
思路：

用快慢指针的思想：
快指针走两步，慢指针只走一步。
如果这个链表是一个环，那么快指针和慢指针总会相遇的。

-快慢指针的原理：

假设快慢指针之间相差n步，
慢指针先走一步，那么快慢指针相差n+1步
然后快指针走两步，那么快慢指针相差n+1-2 = n-1步；
也就是说，每走一次，快慢指针的距离就减少一次；
那么走到n次的时候，快慢指针的相差就为0.

ios代码实现
（1）创建一个链表的类，如下：

@interface Node : NSObject

@property (nonatomic, assign) int value;
@property (nonatomic, strong) Node *next;

@end

（2）快慢指针的实现：

- (BOOL)isCycleNode:(Node *)node {
    if (node == nil && node.next == nil) {
        return NO;
    }
    
    Node *slow = node;
    Node *fast = node.next;
    while (fast != nil && fast.next != nil) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return YES;
        }
    }
   
    return NO;
}

(3)验证：

	Node *node = [[Node alloc] init];
     Node *node1 = [[Node alloc] init];
     Node *node2 = [[Node alloc] init];
     Node *node3 = [[Node alloc] init];
     Node *node4 = [[Node alloc] init];
     
     node4.value = 4;
     node3.value = 3;
     node2.value = 2;
     node1.value = 1;
     node.value = 0;
     
     node4.next = node3;
     node3.next = node2;
     node2.next = node1;
     node1.next = node;
    node.next = node3;

    if ([self isCycleNode:node1]) {
        NSLog(@"----YES---");
    }else {
        NSLog(@"---NO---");
    }