《leetCode-php》链表中环的入口

Given a linked list,return the node where the cycle begins. If there is no cycle,returnnull.

Follow up:

Can you solve it without using extra space?

不使用额外空间判断一个链表是否有环,虽然说的是不使用额外空间，但是还是需要一个变量来实现快慢指针

拥有环形的链表拥有一个特点，推导过程如下

起始节点为X，环形开始节点为Y，快慢指针第一次相交节点为Z，X->Y的距离为a，Y->Z的距离为b，Z->Y的距离为c.

(a+b)*2=a+b+c+b => a=c?

class ListNode {

public $next = null;

public $val;

public function __construct($val) {

$this->val = $val;

}

}

function detectCycle($headNode) {

$node1 = $headNode->next->next;

$node2 = $headNode->next;

while ($node1 !== null && $node2 !== null) {

if ($node1 === $node2) {

while ($node2 !== $headNode) {

$node2 = $node2->next;

$headNode = $headNode->next;

}

return $node2;

}

$node1 = $node1->next->next;

$node2 = $node2->next;

}

return null;

}

$node1 = new ListNode(1);

$node2 = new ListNode(2);

$node3 = new ListNode(3);

$node4 = new ListNode(4);

$node5 = new ListNode(5);

$node6 = new ListNode(6);

$node1->next = $node2;

$node2->next = $node3;

$node3->next = $node4;

$node4->next = $node5;

$node5->next = $node3;

$node = detectCycle($node1);

print_r($node->val);

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!