首页  

快慢指针的妙用     所属分类 algo 浏览量 148
单链表
判断链表是否有环
快速定位中间节点


public class FastAndSlowPoint {

    public static void main(String[] args) throws Exception {

        LinkNode node1 = new LinkNode(1);
        LinkNode node2 = new LinkNode(2);
        LinkNode node3 = new LinkNode(3);

        node1.next = node2;
        node2.next = node3;

        System.out.println(middleNode(node1));
        System.out.println(hasCycle(node1));

        node3.next = node1;
        System.out.println(hasCycle(node1));

        LinkNode node4 = new LinkNode(4);
        node3.next = node4;
        System.out.println(middleNode(node1));
        System.out.println(hasCycle(node1));

    }

    public static LinkNode middleNode(LinkNode head) {
        if (head == null) {
            return null;
        }
        LinkNode slow = head;
        LinkNode fast = head;
        while (fast != null) {
            if (fast == null || fast.next == null) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static boolean hasCycle(LinkNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        LinkNode p = head;
        LinkNode q = head.next;
        while (q != null && q.next != null) {
            if (p == q) {
                return true;
            }
            p = p.next;
            q = q.next.next;
        }
        return false;
    }
}


完整代码
https://gitee.com/dyyx/algo/blob/master/src/main/java/dyyx/FastAndSlowPoint.java


https://leetcode-cn.com/problems/middle-of-the-linked-list/
https://leetcode-cn.com/problems/linked-list-cycle/

上一篇     下一篇
geohash简介

根据经纬度计算距离

二叉树遍历

MySQLTEXT类型最大长度

高效会议六大原则

mysql 单引号转义