本文為原創(chuàng)文章，轉(zhuǎn)載請注明出處，謝謝你……
喜歡java并發(fā)編程的請加群：736156823
開始-->

判斷鏈表中是否有環(huán)。

通過改動算法，可以達到去除鏈表中環(huán)的目的（本文章不提供改動）。

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;
            // 處理長度遠大于環(huán)長度的情況
            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 {

        // 環(huán)的開始節(jié)點
        private final Node start;
        // 環(huán)的結(jié)束節(jié)點
        private final Node end;
        // 環(huán)的長度
        private final int loopLength;
        // 是否存在環(huán)
        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：節(jié)點

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：鏈表創(chuàng)建類

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并發(fā)編程的請加群：736156823
有問題歡迎指正，這是新鮮出爐的
結(jié)束-->
本文為原創(chuàng)文章，轉(zhuǎn)載請注明出處，謝謝你……