醉丶春风的Blog

千里之行, 始于足下



php判断单链表是否有环和相交


前言

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

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

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/


作者: 徐善通
地址: https://www.xstnet.com/article-120.html
声明: 除非本文有注明出处,否则转载请注明本文地址


我有话说



最新回复


正在加载中....

Copyrights © 2016-2019 醉丶春风 , All rights reserved. 皖ICP备15015582号-1