环形链表_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 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

/*
解题思路：
    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;
    }
}

来源：https://www.cnblogs.com/pfzhang18/p/16129084.html
本站部分图文来源于网络，如有侵权请联系删除。