判断链表是否有环,用OC实现
时间: 2024-05-26 19:04:11 浏览: 92
可以使用快慢指针的方式来判断链表是否有环。具体实现如下:
```Objective-C
// 链表的节点
@interface ListNode : NSObject
@property (nonatomic, strong) id value;
@property (nonatomic, strong) ListNode *next;
@end
@implementation ListNode
@end
// 判断链表是否有环
BOOL hasCycle(ListNode *head) {
if (head == nil || head.next == nil) {
return NO;
}
ListNode *slow = head;
ListNode *fast = head.next;
while (slow != fast) {
if (fast == nil || fast.next == nil) {
return NO;
}
slow = slow.next;
fast = fast.next.next;
}
return YES;
}
```
以上代码中,我们使用两个指针slow和fast,开始时它们都指向链表的头节点。slow每次移动一步,fast每次移动两步。如果链表中存在环,则快指针会追上慢指针,并且两个指针会相遇。如果链表中不存在环,则快指针会先到达链表的末尾,此时可以判断链表没有环。
使用示例:
```Objective-C
ListNode *node1 = [[ListNode alloc] init];
node1.value = @(1);
ListNode *node2 = [[ListNode alloc] init];
node2.value = @(2);
ListNode *node3 = [[ListNode alloc] init];
node3.value = @(3);
ListNode *node4 = [[ListNode alloc] init];
node4.value = @(4);
[node1 setNext:node2];
[node2 setNext:node3];
[node3 setNext:node4];
// Uncomment the below line to create a cycle
//[node4 setNext:node2];
BOOL hasCycleResult = hasCycle(node1);
NSLog(@"链表是否有环:%d", hasCycleResult);
```
在上面的示例中,我们创建了一个包含4个节点的链表,并且没有环。通过调用`hasCycle`方法判断链表是否有环,最后输出结果为`NO`。
如果你想测试有环的情况,可以取消注释代码中的一行,将第四个节点的下一个节点指向第二个节点,然后再次运行程序,输出结果将为`YES`。
阅读全文