如何求单向链表是否有环，如果有的话求环的长度以及这个单向链表的长度

2019-11-29

1.下图为这个表的结构以及问题

2.首先要确定这个链表有没有环

思路的话不难，都知道如果有环的话那么遍历这个链表则是没有结尾的，而且最后面的肯定是重复的，最直接想到的就是穷举法，对于上图个数不多的还好，如果表是特别长的话就蛋疼了，那再换个切入点，上学时都跑过三千米吧，第一能把倒数第一落下几圈，是不是有思路了，就是可以定义快慢两个指针，如果有环的话则快慢指针总会能相遇，否则的话这两个指针永远相遇不了。思路有了下一步就是编码了。

//构造数据结构，链表不知道是什么类型的，这里用了一个泛型
//单向链表
    class Node<T>(
            //当前data值
            var data: T? = null,
            //指向下一个的指针
            var next: Node<T>? = null) {
        override fun toString(): String {
            return "Node(data=$data, next=$next)"
        }
    }
    
//再来就是判断一个链表是否有环
fun <T> hasCycle(node: Node<T>): Boolean {
        //先定义两个指针，一个慢指针，一个快指针，让慢指针去碰撞快指针
        //慢指针
        var firstNode = node
        //快指针
        var secondNode = node
        //死循环
        while (true) {
            if (firstNode.next == null) {
                return false
            }
            if (secondNode.next == null) {
                return false
            }
            if (secondNode.next!!.next == null) {
                return false
            }
            firstNode = firstNode.next!!
            secondNode = secondNode.next!!.next!!
            if (firstNode == secondNode) {
                //快慢指针相遇则证明有环
                return true
            }
        }
    }

3.求这个链表的长度

这个思路也很简单，求出那个结环的Node就可以了，第一反应应该就是上一步的相遇点不就是么，但是再仔细想想是不是感觉不是，有可能是环里面的任何一个元素，那么ok换个思路，还是类比以上的思路，先求出这个环的长度，然后还是两个指针步长相同，先让其中一个指针先走环的长度，然后再让两个一起按照一个步长走，那么碰撞时的相遇点就是要求的Node

//第一步先求环的长度，思路比较简单
//首先还是要快慢指针相遇，此时快指针固定，慢指针继续走，再次相遇就是环的长度
fun <T> findCycleLength(node: Node<T>): Int {
        var circleLength = 0
        var firstNode = node
        var secondNode = node
        var hasCircle = false
        while (true) {
            if (firstNode.next == null) {
                return circleLength
            }
            if (secondNode.next == null) {
                return circleLength
            }
            if (secondNode.next!!.next == null) {
                return circleLength
            }
            if (!hasCircle) {
                firstNode = firstNode.next!!
                secondNode = secondNode.next!!.next!!
            } else {
                secondNode = secondNode.next!!
            }
            if (firstNode == secondNode) {
                hasCircle = true
                if (hasCircle && circleLength != 0) {
                    return circleLength + 1
                }
            } else {
                if (hasCircle) {
                    circleLength++
                }
            }
        }
    }
    
    
//上面方法求出环的长度，再来求重复的Node
fun <T> findRepetPoint(node: Node<T>, circleLength: Int): Node<T> {
        var front = node
        var back = node
        //前面的先走circleLength
        (0 until circleLength).forEachIndexed { index, i ->
            front = front.next!!
        }
        println(front.data)
        while (true) {
            front = front.next!!
            back = back.next!!
            if (front == back) {
                return front
            }
        }
    }
    
    
//这样这个链表的长度就求出来了

4.总结

查找链表是否有环使用快慢指针比较巧妙，感觉指针游离作比较，源码地址