醉丶春风的Blog

单链表中快慢指针的应用

什么是快慢指针

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2次，慢指针每次向前移动1次

通过快慢指针， 本文我们实现以下功能

• 快速查找一个不定长的链表中位数 (奇数长度返回中间的元素， 偶数长度返回中间两位中的任一一个元素)
• 在O(n)的时间复杂度中查找到倒数第k位的元素
• 在O(n)的时间复杂度中删除到倒数第k位的元素

1. 在有序链表中寻找中位数

常规的做法是： 先遍历一次链表，拿到链表的length, 再次遍历链表，位于length/2的元素就是中位数
假如只能遍历一次呢， 这个时候就可以用快慢指针来实现了

用法说明

先定义两个指针分别指向head, 遍历链表时，快指针每次移动2, 慢指针每次移动1, 当快指针到达链表末尾时， 慢指针必然指向链表的中间元素

这里有以下两种情况：

• 当快指针指向null时， 代表该链表的长度是奇数， 此时慢指针指向正中间的元素
• 当快指针指向最后一个元素时， 代表该链表的长度是偶数， 此时慢指针指向左边的中位数

如下图：

奇数长度的链表

偶数长度的链表

代码实现, 完整代码请看最下方

/**
 * 获取链表中间的元素
 * 当链表长度为偶数时, 返回 length/2 元素
 * 当链表长度为奇数时, 返回 中间的元素
 * @return bool|null
 */
public function getMiddleNode()
{
    $fast = $this->head;
    $slow = $this->head;

    if ($this->head->next === null) {
        return false;
    }
    // 快指针=null， 或者快指针->next=null 说明快指针走到了终点
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    return $slow->data;
}

2.在O(n)的时间复杂度中查找到倒数第k位的元素

分析

这里我们也可以用到快慢指针，先让快指针走k-1步，比如k=3, 则快指针先走两步， 然后快慢指针同时每次走一步， 当快指针到达链尾时， 此时慢指针指向的即为倒数第k个元素

如下图所示：

倒数第一个元素为6, 倒数第3个元素即为4, 也就是慢指针指向的元素

代码实现, 完整代码请看最下方

/**
 * 获取链表中倒数第n个的元素
 * @param $num
 * @return mixed
 */
public function getReciprocalNode($num)
{
    if ($this->head->next === null) {
        return false;
    }
    $slow = $this->head;
    $fast = $this->head;

    /**
     * fast 先走n-1步
     */
    for ($i=0; $i<$num-1; $i++) {
        if ($fast->next === null) {
            return false;
        }
        $fast = $fast->next;
    }

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

    return $slow;
}

3. 在O(n)的时间复杂度中删除到倒数第k位的元素

要删除倒数第K位的元素， 我们可以找到倒数第K+1位的元素， 然后更新next指向即可
此时，我们就利用到了上一个获取倒数第k个元素的方法 找到倒数K+1的元素

代码实现, 完整代码请看最下方

/**
 * 删除链表中倒数第n个元素
 * 实现起来很简单, 找到 倒数第n+1个元素, 将指针指向->next->next即可
 * @param $num
 * @return bool
 */
public function deleteReciprocalNode($num)
{
    $node = $this->getReciprocalNode($num + 1);
    if ($node !== false) {
        $node->next = $node->next->next;
        return true;
    }
    return false;
}

举一反三

• 如何判断链表中是否有环呢(后半部分是否有循环链表， 也可以从链头开始)
• 如何使用链表来判断是否为回文字符串呢
• 如何判断两个链表是否相交呢

此处下篇文章再讲解，大家可以自己思考一下

附完整代码

元素节点类Ｎode

class Node {

    public $data;

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

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

链表类

class LinkedList {

    /**
     * @var Node
     */
    public $head;

    public function __construct()
    {
        $this->head = new Node();
    }

    public function clear()
    {
        $this->head->next = null;
    }

    public function insert($data)
    {
        $current = $this->head;

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

        $current->next = new Node($data);

        return $this;
    }

    public function getLength()
    {
        $length = 0;
        $current = $this->head->next;
        while ($current !== null) {
            $current = $current->next;
            $length ++;
        }

        return $length;
    }

    public function printAll()
    {
        echo '<hr>';
        $current = $this->head->next;
        while ($current !== null) {
            echo $current->data;
            echo '<br>';
            $current = $current->next;
        }
    }

/**
 * 获取链表中间的元素
 * 当链表长度为偶数时, 返回 length/2 元素
 * 当链表长度为奇数时, 返回 中间的元素
 * @return bool|null
 */
public function getMiddleNode()
{
    $fast = $this->head;
    $slow = $this->head;
    if ($this->head->next === null) {
        return false;
    }

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

    return $slow->data;
}

    /**
     * 获取链表中倒数第n个的元素的数据
     * @param $num
     * @return bool
     */
    public function getReciprocalData($num)
    {
        $result = $this->getReciprocalNode($num);
        if ($result !== false) {
            return $result->data;
        }

        return false;
    }

    /**
     * 获取链表中倒数第n个的元素
     * @param $num
     * @return mixed
     */
    public function getReciprocalNode($num)
    {
        if ($this->head->next === null) {
            return false;
        }
        $slow = $this->head;
        $fast = $this->head;

        /**
         * fast 先走n-1步
         */
        for ($i=0; $i<$num-1; $i++) {
            if ($fast->next === null) {
                return false;
            }
            $fast = $fast->next;
        }

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

        return $slow;
    }



    /**
     * 删除链表中倒数第n个元素
     * 实现起来很简单, 找到 倒数第n+1个元素, 将指针指向->next->next即可
     * @param $num
     * @return bool
     */
    public function deleteReciprocalNode($num)
    {
        $node = $this->getReciprocalNode($num + 1);
        if ($node !== false) {
            $node->next = $node->next->next;
            return true;
        }
        return false;
    }

}

$linkList = new LinkedList();
$linkList->insert(1)
    ->insert(2)
    ->insert(3)
    ->insert(4)
    ->insert(5)
    ->printAll();

echo '倒数第5个元素为: ' . $linkList->getReciprocalData(5) . '<br>';
echo '倒数第1个元素为: ' . $linkList->getReciprocalData(1) . '<br>';
echo '倒数第3个元素为: ' . $linkList->getReciprocalData(3) . '<br>';

// 删除倒数第5个元素
$linkList->deleteReciprocalNode(5);
$linkList->printAll();

// 获取链表中间元素abba
echo '中间元素为' . $linkList->getMiddleNode();

$linkList->insert(10)
    ->insert(11)
    ->insert(12)
    ->printAll();
echo '中间元素为' . $linkList->getMiddleNode();