leetcode — linked-list-cycle

/**
 * Source : https://oj.leetcode.com/problems/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?
 */
public class LinkedListCycle {

    /**
     * 判斷一個連結清單是否有循環
     *
     * 周遊連結清單，将所有周遊過的ndeo放入hash表，如果目前節點已經在hash表中，說明有循環，直到周遊結束。
     *
     * 上線的方法需要額外的空間，使用雙指針法：
     * slow指針每次移動一個node，fast每次移動兩個node，在周遊結束前，如果slow == fast，那麼該連結清單是循環的
     *
     *
     * @param head
     * @return
     */
    public boolean hasCycle (LinkedNode head) {
        if (head == null) {
            return false;
        }
        LinkedNode slow = head;
        LinkedNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    private class LinkedNode {
        int value;
        LinkedNode next;

    }

    /**
     * 建立普通的連結清單
     * @param arr
     * @return
     */
    public LinkedNode createList (int[] arr) {
        if (arr.length == 0) {
            return null;
        }
        LinkedNode head = new LinkedNode();
        head.value = arr[0];
        LinkedNode pointer = head;
        for (int i = 1; i < arr.length; i++) {
            LinkedNode node = new LinkedNode();
            node.value = arr[i];
            pointer.next = node;
            pointer = pointer.next;
        }
        return head;
    }

    /**
     * 将連結清單變為循環連結清單，循環起始為第index個node
     * @param head
     * @param index
     */
    public void makeCycle (LinkedNode head, int index) {
        if (head == null) {
            return;
        }
        LinkedNode tail = head;
        int count = 1;
        while (tail.next != null) {
            tail = tail.next;
            count++;
        }
        LinkedNode p = head;
        if (index > count) {
            index = index % count;
        } else if (index < 0) {
            index = Math.abs(index);
        }
        while (p != null) {
            index--;
            if (index < 1) {
                tail.next = p;
                break;
            }
            p = p.next;
        }

    }

    public static void main(String[] args) {
        LinkedListCycle linkedListCycle = new LinkedListCycle();
        LinkedNode list = linkedListCycle.createList(new int[]{1,2,3,4,5});

        System.out.println(linkedListCycle.hasCycle(list) + " == false");

        linkedListCycle.makeCycle(list, 2);
        System.out.println(linkedListCycle.hasCycle(list) + " == true");
    }
}
           

轉載于:https://www.cnblogs.com/sunshine-2015/p/7906564.html