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;
        }
}