如何找到包含循环(循环)的链表的长度☆☆☆☆

作者 : IT 大叔 本文共2084个字,预计阅读时间需要6分钟 发布时间: 2020-10-13

主题:链表

回答:

  1. 要找到循环的长度,请使用Tortoise和Hare算法
  • 指针A每次前进一(1)个节点。
  • 指针B每次提前两(2)个节点。
  • 从头开始,它们同时前进,直到B命中null(无循环)或AB指向同一节点。
  1. 现在,只有A前进,A会再次遇到B。从您可以找到循环发言权的长度大号
  2. 从头开始,这次有一个指针C首先前进L个节点,然后是指针D在它后面,每个指针一次前进一个节点。
  3. 当它们满足时,行进的节点D的数量L0L等于带循环的链表长度

实现方式:

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)
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 如何找到包含循环(循环)的链表的长度☆☆☆☆

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论