如何找到包含循环（循环）的链表的长度☆☆☆☆

主题：链表

回答：

要找到循环的长度，请使用Tortoise和Hare算法：

指针A每次前进一（1）个节点。
指针B每次提前两（2）个节点。
从头开始，它们同时前进，直到B命中null（无循环）或A和B指向同一节点。

现在，只有A前进，A会再次遇到B。从您可以找到循环发言权的长度大号。
从头开始，这次有一个指针C首先前进L个节点，然后是指针D在它后面，每个指针一次前进一个节点。
当它们满足时，行进的节点D的数量L0加L等于带循环的链表的长度。

实现方式：

JAVA

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;
    }
}

Y

nodes = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 2)]

def next(parent):
  def find(nodes, parent):
    current = nodes[0]
    rest = nodes[1:]

    if current and current[0] == parent:
      return current[1]
    else:
      return find(rest, parent)
  return find(nodes, parent) 

def next_next(x):
  return next(next(x))

def meet(slow, fast, p1, p2, steps):
  p1 = slow(p1)
  p2 = fast(p2)
  steps = steps + 1

  if p1 == p2:
    return (p1, steps)
  else:
    return meet(slow, fast, p1, p2, steps)

def meet_result(slow, fast, p1, p2):
  result = meet(slow, fast, p1, p2, 0)
  return result[0]

def meet_count(slow, fast, p1, p2):
  result = meet(slow, fast, p1, p2, 0)
  return result[1]

def find_cycle(init):
  cycle_meet = meet_result(next, next_next, init, init)
  cycle_root = meet_result(next, next, cycle_meet, init)
  cycle_length = meet_count(lambda x: x, next, cycle_root, cycle_root)
  return (cycle_meet, cycle_root, cycle_length)

常见问题FAQ