第八周 - 习题

用户头像
而立
关注
发布于: 13 小时前

习题内容

有两个单项链表(链表长度分别为m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是途中的X元素。



代码实现

class Node
{
public $value = null;
public $nextNode = null;
}
class ListManager
{
public $listoneFirstNode;
public $listTwoFirstNode;
private function addNode(&$nodeNow, $value)
{
while (true) {
if (is_null($nodeNow)) {
$nodeNow = new Node();
$nodeNow->value = $value;
break;
}
$nodeNow = &$nodeNow->nextNode;
}
}
/**
* 向第一个list添加元素
* @param $value
*/
public function addFirtListNode($value)
{
$this->addNode($this->listoneFirstNode, $value);
}
/**
* 向第二个list添加元素
* @param $value
*/
public function addTwoListNode($value)
{
$this->addNode($this->listTwoFirstNode, $value);
}
/**
* 查找两个链表的交叉点
* @return |null
*/
public function findOverlappingEle()
{
//遍历第一条list
$nodeNowOneList = $this->listoneFirstNode;
while (true) {
if (is_null($nodeNowOneList)) {
break;
}
//遍历第二条list
$nodeNowSecondList = $this->listTwoFirstNode;
//遍历第二条list
while (true) {
if (is_null($nodeNowSecondList)) {
break;
}
//如果当前值相同,则判断后续的值是否都相同
if ($nodeNowSecondList->value == $nodeNowOneList->value) {
//相同,则进入后续校验
if ($this->checkIfOverlappingEle($nodeNowOneList, $nodeNowSecondList)) {
return $nodeNowSecondList->value;
}
}
//继续下一个节点
$nodeNowSecondList = $nodeNowSecondList->nextNode;
}
$nodeNowOneList = $nodeNowOneList->nextNode;
}
return null;
}
/**
* 判断当前两个节点以及其后的节点是否都相同
* @param $nodeOne
* @param $nodeTwo
* @return bool
*/
private function checkIfOverlappingEle($nodeOne, $nodeTwo): bool
{
while (true) {
if (is_null($nodeOne) && is_null($nodeTwo)) {
return true;
} else if ((is_null($nodeOne) && !is_null($nodeTwo))
|| (is_null($nodeTwo) && !is_null($nodeOne))
|| $nodeOne->value != $nodeTwo->value) {
return false;
}
$nodeOne = $nodeOne->nextNode;
$nodeTwo = $nodeTwo->nextNode;
}
}
}

分析

实现思路,是遍历一条list,每移动一个节点,在另一条list上寻找和当前节点值一样的第一个节点。

找到这个节点之后,将当前两个节点传入一个判断函数,该判断函数检查当前两个节点以及其后缀节点是否完全相同。

如果完全相同,那么就是交叉点。

时间复杂度是O(n3),n的立方。

其他解法

当然,如果没有存储限制,还有别的解决办法。

可以先将两条list倒置,生成两个逆向的list。然后从前往后同时遍历两条逆向的list,第一个不相同的节点的上一个节点就是交叉点。

用户头像

而立

关注

还未添加个人签名 2018.01.25 加入

还未添加个人简介

评论

发布
暂无评论
第八周-习题