本文为原创文章，转载请注明出处，谢谢你……
喜欢java并发编程的请加群：736156823
开始-->

判断链表中是否有环。

通过改动算法，可以达到去除链表中环的目的（本文章不提供改动）。

public class FindLoop {

    private FindLoop() {

    }

    public static final FindLoop create() {
        return new FindLoop();
    }

    public final LoopStructure getLoop(Node head) {
        if (null == head) {
            return noLoop();
        }
        Node temp = head;
        if (null == temp.getNext()) {
            return noLoop();
        }
        Node slow = head;
        Node fast = head;
        boolean has = false;
        for (; null != fast.getNext() && null != fast.getNext().getNext(); ) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
            if (slow == fast) {
                has = true;
                break;
            }
        }
        if (has) {
            int count = 0;
            Node loopLenFlag = slow;
            // 处理长度远大于环长度的情况
            boolean meetLoopLenFlag = false;
            Node endFlag = fast;
            slow = head;
            for (; fast != slow; ) {
                slow = slow.getNext();
                fast = fast.getNext();
                if (endFlag.getNext() != fast) {
                    endFlag = endFlag.getNext();
                }
                if (fast != loopLenFlag) {
                    if (!meetLoopLenFlag) {
                        count++;
                    }
                } else {
                    if (!meetLoopLenFlag) {
                        count++;
                        meetLoopLenFlag = true;
                    }
                }
            }
            Node start = slow;
            Node end = endFlag;
            if (!meetLoopLenFlag) {
                for (; fast != loopLenFlag; ) {
                    fast = fast.getNext();
                    count++;
                }
            }
            return LoopStructure.create(start, end, count, true);
        } else {
            return noLoop();
        }
    }

    private final LoopStructure noLoop() {
        return LoopStructure.create(null, null, 0, false);
    }


    public static final void main(String args[]) {
        FindLoop findLoop = FindLoop.create();
        Node loop = CreateList.create().buildLoop(1189000, 78);
        LoopStructure structure = findLoop.getLoop(loop);
        System.out.println("loop is in list=" + structure.isHasLoop());
        System.out.println("loop length=" + structure.getLoopLength());
        System.out.println("loop start data=" + structure.getStart().getDate());
        System.out.println("loop end data=" + structure.getEnd().getDate());
    }

    private static final class LoopStructure {

        // 环的开始节点
        private final Node start;
        // 环的结束节点
        private final Node end;
        // 环的长度
        private final int loopLength;
        // 是否存在环
        private final boolean hasLoop;

        private LoopStructure(Node start, Node end, int loopLength, boolean hasLoop) {
            this.start = start;
            this.end = end;
            this.loopLength = loopLength;
            this.hasLoop = hasLoop;
        }

        public static final LoopStructure create(Node start, Node end, int loopLength, boolean hasLoop) {
            return new LoopStructure(start, end, loopLength, hasLoop);
        }

        public Node getStart() {
            return start;
        }

        public Node getEnd() {
            return end;
        }

        public int getLoopLength() {
            return loopLength;
        }

        public boolean isHasLoop() {
            return hasLoop;
        }
    }

}

[Floyd's cycle-finding algorithm]
(https://stackoverflow.com/questions/3880735/floyds-cycle-finding-algorithm)

辅助工具类1：节点

public class Node {

    private Node next;
    private int date;

    private Node() {

    }

    public static final Node create() {
        return new Node();
    }

    public void setNext(final Node next) {
        this.next = next;
    }

    public Node getNext() {
        return next;
    }

    public int getDate() {
        return date;
    }

    public void setDate(int date) {
        this.date = date;
    }

    @Override
    public String toString() {
        return "Node{" +
                "date=" + date +
                '}';
    }
}

辅助工具类2：链表创建类

public class CreateList {

    private CreateList() {

    }

    public static final CreateList create() {
        return new CreateList();
    }

    public final Node buildNormal(int length) {
        return build(length).getHead();
    }

    private final HeadTail build(int length) {
        final Node head = Node.create();
        Node current = head;
        for (int i = 0; i < length; i++) {
            Node node = Node.create();
            node.setDate(i + 1);
            current.setNext(node);
            current = node;
        }
        final HeadTail ht = HeadTail.create(head, current);
        return ht;
    }

    public final Node buildLoop(int listLength, int loopLength) {
        if (listLength < 0) {
            throw new IllegalArgumentException();
        }
        if (listLength == 0) {
            return Node.create();
        }
        if (loopLength <= 0) {
            return buildNormal(listLength);
        }
        if (loopLength > listLength) {
            throw new IllegalArgumentException();
        }
        HeadTail ht = build(listLength);
        Node head = ht.getHead();
        Node tail = ht.getTail();
        if (loopLength == listLength) {
            tail.setNext(head.getNext());
        } else {
            Node temp = head;
            int dur = listLength - loopLength;
            for (int i = 0; i < dur; i++) {
                temp = temp.getNext();
            }
            tail.setNext(temp.getNext());
        }
        return head;
    }

    private static final class HeadTail {
        private final Node head;
        private final Node tail;

        private HeadTail(final Node head, final Node tail) {
            this.head = head;
            this.tail = tail;
        }

        public static final HeadTail create(final Node head, final Node tail) {
            return new HeadTail(head, tail);
        }

        public Node getHead() {
            return head;
        }

        public Node getTail() {
            return tail;
        }
    }

}

运行截图

image.png

喜欢java并发编程的请加群：736156823
有问题欢迎指正，这是新鲜出炉的
结束-->
本文为原创文章，转载请注明出处，谢谢你……