08.取出有环链表中环的长度

目录介绍

  • 01.题目要求
  • 02.问题分析
  • 03.实例代码

01.题目要求

  • 如下所示
    • image
      image
    • image
      image

02.问题分析

  • 这里面，我们需要先判断链表是否有环，这个方法的返回值是boolean型，但是现在要把这个方法稍做修改，让其返回值为相遇的那个结点。然后，我们拿到这个相遇的结点就好办了，这个结点肯定是在环里嘛，我们可以让这个结点对应的指针一直往下走，直到它回到原点，就可以算出环的长度了。

03.实例代码

  • 代码如下所示
    public class LinkList {
    public Node head;
    public Node current;

    public int size;

    //方法：向链表中添加数据
    public void add(int data) {
        //判断链表为空的时候
        if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
            head = new Node(data);
            current = head;
        } else {
            //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
            current.next = new Node(data);
            //把链表的当前索引向后移动一位
            current = current.next;   //此步操作完成之后，current结点指向新添加的那个结点
        }
    }


    //方法重载：向链表中添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (head == null) {
            head = node;
            current = head;
        } else {
            current.next = node;
            current = current.next;
        }
    }


    //方法：遍历链表（打印输出链表。方法的参数表示从节点node开始进行遍历
    public void print(Node node) {
        if (node == null) {
            return;
        }

        current = node;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    //方法：判断单链表是否有环。返回的结点是相遇的那个结点
    public Node hasCycle(Node head) {

        if (head == null) {
            return null;
        }

        Node first = head;
        Node second = head;

        while (second != null) {
            first = first.next;
            second = second.next.next;

            if (first == second) {  //一旦两个指针相遇，说明链表是有环的
                return first;  //将相遇的那个结点进行返回
            }
        }

        return null;
    }

    //方法：有环链表中，获取环的长度。参数node代表的是相遇的那个结点
    public int getCycleLength(Node node) {

        if (head == null) {
            return 0;
        }

        Node current = node;
        int length = 0;

        while (current != null) {
            current = current.next;
            length++;
            if (current == node) {  //当current结点走到原点的时候
                return length;
            }
        }

        return length;
    }

    class Node {
        //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
        int data; //数据域
        Node next;//指针域

        public Node(int data) {
            this.data = data;
        }
    }
}
  • 测试代码，获取相遇的那个结点
    public void test() {
        LinkList list1 = new LinkList();
        Node second = null; //把第二个结点记下来
        //向LinkList中添加数据
        for (int i = 0; i < 4; i++) {
            list1.add(i);
            if (i == 1) {
                second = list1.current;  //把第二个结点记下来
            }
        }
        list1.add(second);  
        //将尾结点指向链表的第二个结点，于是单链表就有环了，备注：此时得到的环的结构，是本节中图2的那种结构
        Node current = list1.hasCycle(list1.head);  //获取相遇的那个结点
        System.out.println("环的长度为" + list1.getCycleLength(current));
}

//打印值：3
  • 测试代码，将头结点添加到链表当中
    public void test() {
    LinkList list1 = new LinkList();
    //向LinkList中添加数据
    for (int i = 0; i < 4; i++) {
        list1.add(i);
    }
    list1.add(list1.head); //将头结点添加到链表当中（将尾结点指向头结点），于是，单链表就有环了。备注：此时得到的这个环的结构，是本节中图1的那种结构。
    Node current = list1.hasCycle(list1.head);
    System.out.println("环的长度为" + list1.getCycleLength(current)); 
}

//打印值：4
贡献者: yangchong211