day151-LeetCode 141. Linked List Cycle

题目

Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?

分析

求链表中是否有个循环

题解

/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
function hasCycle (head) {
if (head === null || head.next === null) {
return false
}
let node = head
while (node !== null) {
if (node.flag) {
return true
}
// 标记节点每一个跑过的节点
node.flag = true
// 跑到下一个节点
node = node.next
}
return false
}

快慢链表

两者步长不一样

public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;

if (slow == fast)
return true;
}

return false;
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/06/13/2019-06-13/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog