php判断单链表是否有环和相交- 醉丶春风的Blog

前言

前面几个文章讲了单链表和快慢指针的用法，这里再延伸一下快慢指针的用法
本文讲解三个例子：

给定一个单链表，判断是否有环(链表后部分存在循环，或者就是一个循环链表)
如果有环，找到环的入口
判断两个单链表是否相交

1.判断单链表是否有环

如果一个链表存在循环，则代表该链表有环，其中，可能是部分循环，也可能是首尾相接的循环链表，如下图

在后面形成环的单链表

alt

首尾相接的循环单链表

alt

解析

这里我们还需要用到快慢指针，快慢指针同时从链表头出发，快指针每次走2步，慢指针每次走1步，当快指针走到了末尾时，代表该链表不是环形链表
反之，当快指针追上了慢指针，则代表该链表是环形链表

理解这个就好像我们在操场跑步一样，跑道是环形的，两个人赛跑，一个跑的快，一个跑的慢，如果我们不让他停下来，跑的快的人总会'追'上跑的慢的人

比如第一张图片，我们可以推导出：
fast->2->4->6->3->5
slow->1->2->3->4->5
当慢指针走到5时，快慢指针相遇，则这个链表是环形链表

下面我们就使用代码来实现验证是否为有环的单链表

代码实现，完整代码在最下面

/**
 * 判断链表是否有环
 * @param $head
 * @return bool
 */
public function isCycleLinkedList($head)
{
    $fast = $head;
    $slow = $head;

    while ($fast !== null && $fast->next !== null) {
        $fast = $fast->next->next;
        $slow = $slow->next;
        if ($fast === $slow) {
            return true;
        }
    }
    return false;
}

2. 如果有环，找到环的入口

分析

由上题可知，按照快指针每次走2步，慢指针每次走1步的方式，发现快指针和慢指针重合，确定了单向链表有环路了。接下来，让快指针回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当快指针和慢指针再次相遇的时候，就是环路的入口了。

代码实现

/**
 * 判断链表是否有环， 并找到环的入口
 * @param $head
 * @return bool
 */
public function findLoopEntrance($head)
{
    $fast = $head;
    $slow = $head;

    // 先判断是否有环
    while ($fast != null && $fast->next !== null) {
        $fast = $fast->next->next;
        $slow = $slow->next;
        if ($fast === $slow) {
            break;
        }
    }
    if ($fast === null || $fast->next === null) {
        return false;
    }

    $fast = $head;
    while ($fast !== $slow) {
        $fast = $fast->next;
        $slow = $slow->next;
    }
    return $fast->data;
}

3. 判断两个单链表是否相交

这里我们就不考虑链表有环的问题了(其实是我不想去研究了，下次有时间了再画图补上)
假设两个单链表都没有环，如果他们相交，则他们的尾指针一定是相同的，我们只要比较两个链表的尾结点即可，如下图：

alt

代码实现

/**
 * 判断两个链表是否相交
 * @param $l1
 * @param $l2
 * @return bool
 */
public function isIntersect($l1, $l2)
{
    if ($l1 == null || $l2 == null) {
        return false;
    }

    while ($l1->next !== null) {
        $l1 = $l1->next;
    }

    while ($l2->next !== null) {
        $l2 = $l2->next;
    }

    return $l1 === $l2;
}

假如链表有环，判断是否相交

。。。。

完整代码

<?php
/**
 * Created by PhpStorm.
 * Author: Xu shantong <shantongxu@qq.com>
 * Date: 19-8-10
 * Time: 下午3:09
 */

class Node {
    /**
     * @var mixed data
     */
    public $data;

    /**
     * @var self $next
     */
    public $next = null;

    public function __construct($data, $next = null)
    {
        $this->data = $data;

        $this->next = $next;
    }
}

class IsCycleSingleLinkedList {

    /**
     * 判断链表是否有环
     * @param $head
     * @return bool
     */
    public function isCycleLinkedList($head)
    {
        $fast = $head;
        $slow = $head;

        while ($fast !== null && $fast->next !== null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断链表是否有环， 并找到环的入口
     * @param $head
     * @return bool
     */
    public function findLoopEntrance($head)
    {
        $fast = $head;
        $slow = $head;

        // 先判断是否有环
        while ($fast != null && $fast->next !== null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                break;
            }
        }
        if ($fast === null || $fast->next === null) {
            return false;
        }

        $fast = $head;
        while ($fast !== $slow) {
            $fast = $fast->next;
            $slow = $slow->next;
        }
        return $fast->data;
    }

    /**
     * 判断两个链表是否相交
     * @param $l1
     * @param $l2
     * @return bool
     */
    public function isIntersect($l1, $l2)
    {
        if ($l1 == null || $l2 == null) {
            return false;
        }

        while ($l1->next !== null) {
            $l1 = $l1->next;
        }

        while ($l2->next !== null) {
            $l2 = $l2->next;
        }

        return $l1 === $l2;
    }

    //Todo 判断有环链表是否相交
}

$node1 = new Node(1);
$node2 = new Node(2);
$node3 = new Node(3);
$node4 = new Node(4);
$node5 = new Node(5);
$node6 = new Node(6);

$node1->next = $node2;
$node2->next = $node3;
$node3->next = $node4;
$node4->next = $node5;
$node5->next = $node6;
// 第6个节点指向了第三个节点， 形成了循环
$node6->next = $node3;


$linkedList = new IsCycleSingleLinkedList();
// 判断链表是否有环
var_dump($linkedList->isCycleLinkedList($node1)); // true
// 找出环的入口
var_dump($linkedList->findLoopEntrance($node1)); // 3
// 判断两个链表是否相交
$node6->next = null; // 重置node6的指针， 使链表没有环
var_dump($linkedList->isIntersect($node3, $node1)); // true
var_dump($linkedList->isIntersect($node3, new Node(0))); // false
var_dump($linkedList->isIntersect($node3, new Node('head', $node1))); // true

参考 http://wuchong.me/blog/2014/03/25/interview-link-questions/

醉丶春风的Blog

千里之行, 始于足下