環形鏈表_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;
    }
}

標籤：其他

上一篇：Python實作常用的假設檢驗

下一篇：Python+Selenium實作短視頻自動上傳與發布