p141

发表于 | 分类于 |

LeetCode p141 Linked List Cycle 题解

1.题目：

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

题意：

判断一个链表里面是否有环。

2.解题思路:

开始是用HashSet写，但是用了额外的空间。不过是我可以想到的最好的解法了。
然后转换成追及问题（我是这么理解的）。。整个人都开朗了。
如果有环一定会相遇这样~

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
			return false;
		ListNode slow = head;
		ListNode fast = head.next;
		while (fast != null && slow != fast && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}//转换成一个追及相遇问题,如果有环最后会相遇.
		if (fast == slow)
			return true;
		return false;
    }
}

4.一些总结：