public class ReverseLinkedList {

    static class Node {
        int id;
        Node next;

        public Node(int id) {
            this.id = id;
        }
    }

    public static void main(String[] args) {
        print(reverse(buildCycleList()));
        print(reverse(buildNonCycleList()));
    }

    private static Node reverse(Node head) {
        Node circle = findCircle(head);
        Node current = head;
        Node previous = null;
        boolean visited = false;
        do {
            if (current == null)
                break;
            if (current == circle) {
                if (visited)
                    break;
                visited = true;
            }
            var tmp = current.next;
            current.next = previous;
            previous = current;
            current = tmp;
        } while (true);
        return previous;
    }

    private static Node findCircle(Node head) {
        Node tortoise = head;
        Node hare = head;
        do {
            tortoise = move(tortoise);
            hare = move(move(hare));
            if (tortoise == null || hare == null) // no cycle
                return null;
        } while (tortoise != hare);

        tortoise = head;
        while (tortoise != hare) {
            tortoise = move(tortoise);
            hare = move(hare);
        }

        return tortoise;
    }

    private static Node move(Node node) {
        return node != null ? node.next : null;
    }

    private static void print(Node reversed) {
        Node current = reversed;
        while (current != null) {
            System.out.print(current.id + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    private static Node buildCycleList() {
        Node head = new Node(1);
        Node circle = new Node(2);
        head.next = circle;
        circle.next = new Node(3);
        circle.next.next = new Node(4);
        circle.next.next.next = new Node(5);
        circle.next.next.next.next = circle;
        return head;
    }

    private static Node buildNonCycleList() {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        return head;
    }
}