1
[抄题]:
给定一个链表,判断它是否有环。
[思维问题]:
反而不知道没有环怎么写了:快指针fast(奇数个元素)或fast.next(偶数个元素) == null
[一句话思路]:
快指针走2步,慢指针走1步。
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
[总结]:
[复杂度]:Time complexity: O(n) Space complexity: O(1)
[英文数据结构,为什么不用别的数据结构]:
[其他解法]:
[Follow Up]:
[题目变变变]:
2
[抄题]:
返回环的入口
[思维问题]:
[一句话思路]:
背就行
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
[总结]:
[复杂度]:Time complexity: O() Space complexity: O()
[英文数据结构,为什么不用别的数据结构]:
[其他解法]:
[Follow Up]:
[题目变变变]:
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/public class Solution {
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
public boolean hasCycle(ListNode head) {
// write your code here
if (head == null) {
return false;
}
ListNode fast = head.next;
ListNode slow = head;
while(fast != slow) {
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
} while (head != slow.next) {
head = head.next;
slow = slow.next;
}
return head;
}
}