精选算法面试 - 链表（判断环）

李孟

关注

发布于: 2021 年 01 月 09 日

一.简介

链表是通过指针将一组零散的内存串联在一起，因此后继结点有可能指向前驱结点形成环路。

二.示例

2.1 判断链表是否有环

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

解题思路比较巧妙运用快慢指针，快指针是慢指针的二倍，再次相遇时证明链表存在环路，还有的方式比较容易想比如运用结合遍历所有，当循环时判定存在相同结点证明有环，当然这种方式效率不高。

 public boolean hasCycle(ListNode head) {        ListNode node = head;        boolean result = false;        if(node == null){            return result;        }        //快指针        ListNode next = head.next;        if(next == null){            return result;        }        while (next != null && next.next != null){            //快指针与慢指针相遇，证明有环            if(next == node){                result = true;                break;            }            next = next.next.next;            //慢指针            node = node.next;        }        return result;    }

复制代码

2.2 环形链路入口结点

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

返回进入环路的结点，例如：上述图中 2 结点是入口，索引应该是 1。

集合实现方式

public ListNode detectCycle(ListNode head) {        ListNode pos =head;        //通过集合判断是否存在环        Set<ListNode> visited  = new HashSet<>();        while (pos != null){            if(visited.contains(pos)){                return pos;            }else{                visited.add(pos);            }            pos = pos.next;        }        return null;}

复制代码

快慢指针

这个思路比较巧妙，在于需要推导需要满足什么条件可以找到入口条件。

我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

fast 指针走过距离 a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc。

任意时刻 fast 指针走过距离是 slow 的 2 倍。

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n-1)(b+c)a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离。

注意

快针走的是慢针的两倍。
慢针走过的路，快针走过一遍。
快针走过的剩余路程，也就是和慢针走过的全部路程相等。(a+b = c+b)
刨去快针追赶慢针的半圈(b)，剩余路程即为所求入环距离(a=c)

public ListNode detectCycle(ListNode head) {        ListNode node = head;        if(node == null){            return null;        }        ListNode next = head;               while (next != null){            node = node.next;            //快指针            if(next.next != null){                next = next.next.next;             }else{                return null;            }            //快指针与慢指针相遇            if(next == node){                //头结点                ListNode p = head;                //从头结点出发查找迭代到相遇点位置                while(p != node){                    p = p.next;                    node = node.next;                }                return p;            }          }        return null;    }