環形鏈表_141_142

LeetCode_141：https://leetcode-cn.com/problems/linked-list-cycle/

　　給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。

　　如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。

　　如果鏈表中存在環 ，則返回 true 。 否則，返回 false 。

/*
解題思路：快慢指針
    定義兩個指針p，q，都指向head;
    讓p每次向前走一步，q每次向前走兩步，
    如果成環，則它們會相遇，
    如果不成環，則不會。
*/
class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)){
                return true;
            }
        }
        return false;
    }
}

/*
使用哈希表來存儲所有已經訪問過的節點。
每次我們到達一個節點，如果該節點已經存在於哈希表中，則說明該鏈表是環形鏈表，否則就將該節點加入哈希表中。
重覆這一過程，直到我們遍歷完整個鏈表即可。
*/
class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

LeetCode_142：環形鏈表  https://leetcode-cn.com/problems/linked-list-cycle-ii/

給定一個鏈表的頭節點  head ，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

/*
解題思路：
    還是通過快慢指針，根據數學推導，
    當發現 slow 與 fast 相遇時，我們再額外使用一個指針 ptr，
    起始，它指向鏈表頭部；
    隨後，它和 slow 每次向後移動一個位置。
    最終，它們會在入環點相遇。
*/
    
class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

/*
解題思路： 
    我們遍歷鏈表中的每個節點，並將它記錄下來；
    一旦遇到了此前遍歷過的節點，就可以判定鏈表中存在環。
    這裡的記錄，是用contians函數，看是否是同一個。
*/

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

環形鏈表的約瑟夫問題：https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a

/*
解題思路：
    1.初始化：將所有人圍在一起，排列成環，首位相連。
    2.然後進行遍歷操作，遍歷的終止條件是當cur != cur.next，也就是當只有一個節點時退出。
    3.遍歷的過程：從頭結點出發，for迴圈到k的前一個，然後刪除k位置節點。
    4.重覆此操作，直到退出迴圈。
    5.最後返回剩下的節點數據即可;
*/

class Solution {
    public int ysf (int n, int m) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        for(int i = 1; i<=n; i++) {
            ListNode node = new ListNode(i);
            cur.next = node;
            cur = cur.next;
        }
        cur.next = head.next;
        ListNode tmp = head.next;
        while (tmp != tmp.next) {
            for(int i = 1; i< m - 1; i++) {
                tmp = tmp.next;
            }
            tmp.next = tmp.next.next;
            tmp = tmp.next;
        }
        return tmp.val;
    }
}