算法（1） - 链表有环问题

- 日理万妓 2022-09-04 12:44 160阅读 0赞

参考：

*  lubuladong的算法小抄

## 一、链表有环相关算法题 ##

通常有以下问题：

*  1.判断是否有环
 *  2.有环的话，计算环的长度
 *  3.有环的话，找出入环点

有没有环临时还能想出来，2、3要是之前没想过一时半会还真一定想明白，以下就记录一下怎么实现的。

### 1.1 判断链表是否有环 ###

思路：

*  通过快慢指针解决
 *  快指针每次前进2步，慢指针每次前进1步，假如快慢指针相遇，那么就表示有环
 *  （有点类似于追及类问题，跑的快的肯定会追上慢的，被套圈了…）

public static class Node { 
        int value;
        Node next;
        public Node(int value, Node next) { 
            this.value = value;
            this.next = next;
        }
    }
    
    /** * 判断链表是否有环 * * @param head 头结点 * @return */
    public static boolean isCycle(Node head) { 
    	// 定义快慢指针
        Node slow = head;
        Node fast = head;
    
        while (fast != null && fast.next != null) { 
            // 慢指针每次前进1步
            slow = slow.next;
            // 快指针每次前进2步
            fast = fast.next.next;
    
            // 快慢指针相遇了，表示有环
            if (slow == fast) { 
                return true;
            }
        }
        return false;
    }

### 1.2 计算环的长度 ###

思路：沿用快慢指针的思路：

*  第一次相遇：记录相遇过，再走一圈，记录走的步数
 *  第二次相遇：此时相遇，记录的步数就是环长（因为快指针比慢指针快1步，所以多走了一圈）

/** * 环的长度 * * @param head * @return */
    public static int cycleLength(Node head) { 
    	// 快慢指针
        Node slow = head;
        Node fast = head;
    
    	// 环的长度
        int length = 0;
        // 是否相遇过
        boolean meet = false;
        while (fast != null && fast.next != null) { 
            // 慢指针每次前进1步
            slow = slow.next;
            // 快指针每次前进2步
            fast = fast.next.next;
    
            // 已经相遇，慢指针每前进一步：环长度+1
            if (meet) { 
                length++;
            }
    
            // 快慢指针相遇了，表示有环
            if (slow == fast) { 
                if (!meet) { 
                    // 第一次相遇
                    meet = true;
                } else { 
                    // 第二次相遇
                    return length;
                }
            }
        }
        return 0;
    }

### 1.3 找出入环点 ###

思路：沿用快慢指针的思路

*  第一次相遇后，让 快指针或慢指针指向头结点，之后快慢节点都是每次前进1步，再次相遇的节点就是入环点（这个可以通过公式推导出来的，这里就不细讲了）

/** * 找出入环点 * * @param head * @return */
    public static Node findEnter(Node head) { 
    	// 快慢指针
        Node slow = head;
        Node fast = head;
    
        while (fast != null && fast.next != null) { 
            // 慢指针每次前进1步
            slow = slow.next;
            // 快指针每次前进2步
            fast = fast.next.next;
    
            // 快慢指针相遇了，表示有环
            if (slow == fast) { 
                // 慢指针指向头结点
                slow = head;
                // 再次相遇时就是入环点
                while (slow != fast) { 
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

### 1.4 总结 ###

总结一下，链表相关问题一般通过双指针比较容易解决，例如本篇文章的快慢指针，还有一些链表的题目：寻找链表的中点、寻找链表倒数第K个节点等