LeetCode Linked List Cycle & Linked List Cycle II
Linked List Cycle题意：给定一个链表，求这个链表有无循环
解法一：按照题目要求，不用额外空间做，我的想法是如果当前链表是a0->a1-> a2-> a3，那么不妨进行一次遍历，当前为temp，前一个为pre，后一个为next，然后将temp的next指针指向pre，这样一直遍历，如果最后跑到了head，就表示有环，否则无环。有一个bug是head是null的情况需要特判。
//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)
return false;
ListNode pre = head, temp = head.next, next;
head.next = null;
while (temp != null) {
if (temp == head)
return true;
next = temp.next;
if (next == null)
return false;
temp.next = pre;
pre = temp;
temp = next;
}
return false;
}
}
解法二：看到submission里面我的速度有些太慢了，于是百度了一下，发现一个更好的方法。两个指针，fast和slow，fast每次走两个next，slow走一个，当两个相遇的时候就表示有环。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head, slow = head, temp1, temp2;
while (head != null && slow != null) {
slow = slow.next;
temp1 = fast.next;
if (temp1 == null)
return false;
temp2 = temp1.next;
if (temp2 == null)
return false;
fast = temp2;
if (head == slow)
return true;
}
return false;
}
}
Linked List Cycle II 题意：同上，只不过求的是第一个循环的节点
解法：这个按照我自己的解法，拆链没法做了，因为把原有的关系都破坏了。fast和slow的这个经典方法可以，具体的解析这个人写的很好
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode node = hasCycle(head);
if (node == null)
return null;
ListNode temp1 = head, temp2 = node;
while (temp1 != temp2) {
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}
public ListNode hasCycle(ListNode head) {
ListNode fast = head, slow = head, temp1, temp2;
while (head != null && slow != null) {
slow = slow.next;
temp1 = fast.next;
if (temp1 == null)
return null;
temp2 = temp1.next;
if (temp2 == null)
return null;
fast = temp2;
if (fast == slow)
return fast;
}
return null;
}
}
页:
[1]