Find the length of a Linked List which contains cycle (loop)

Technology CommunityCategory: Linked ListsFind the length of a Linked List which contains cycle (loop)
VietMX Staff asked 3 years ago
  1. To find the length of loop apply Tortoise and Hare algorithm:
    • Pointer A advances one (1) node a time.
    • Pointer B advanced two (2) node a time.
    • Start from head, they advanced at the same time until B hit null (no loop) or A and B point to the same node.
  1. Now, has A advances only, A would meet B again. From that you can find the length of the loop say L.
  2. Start from head again, this time have a pointer C advances L nodes first, followed by pointer D behind it, each advances one node at a time.
  3. When they meet, the number of nodes D traveled L0 plus L is equal to the length of the linked list with a loop.
Implementation
package com.farenda.tutorials.algorithms.lists;
 
public class FloydCycleDetector {
 
    private int position;
    private int length;
    private boolean cycle;
    private Node head, tortoise, hare;
 
    public void detect(Node head) {
        this.head = head;
        this.tortoise = this.hare = head;
        this.cycle = detectCycle();
        if (cycle) {
            System.out.println("Found cycle.");
            this.position = findPosition();
            this.length = cycleLength();
        } else {
            System.out.println("No cycle.");
            this.position = -1;
            this.length = 0;
        }
    }
 
    public boolean hasCycle() {
        return cycle;
    }
 
    public int length() {
        return length;
    }
 
    public int position() {
        return position;
    }
 
    private boolean detectCycle() {
        if (tortoise == null || tortoise.next == null) {
            return false;
        }
        while (hare != null && hare.next != null) {
            System.out.printf("(%d, %d),", tortoise.data, hare.data);
            tortoise = tortoise.next;
            hare = hare.next.next;
            if (tortoise == hare) {
                System.out.printf("turtle(%d) == hare(%d)%n",
                        tortoise.data, hare.data);
                return true;
            }
        }
        return false;
    }
 
    private int findPosition() {
        int i = 1;
        tortoise = head;
        System.out.printf("(%d, %d),", tortoise.data, hare.data);
        while (tortoise != hare) {
            tortoise = tortoise.next;
            hare = hare.next;
            ++i;
        }
        return i;
    }
 
    private int cycleLength() {
        int i = 0;
        do {
            hare = hare.next;
            ++i;
        } while (tortoise != hare);
        return i;
    }
}