0%

单链表取中间节点

于千万人之中遇见你所遇见的人,于千万年之中,时间的无涯的荒野里,没有早一步,也没有晚一步,刚巧赶上了,那也没有别的话可说,惟有轻轻的问一声:“哦,你也在这里吗?”

一、概念

  1. 单向链表(单链表)是链表的一种,是由一系列的存储数据元素的单元(通常称为结点node)通过指针串接起来形成的,每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针。

  2. 特性

    • head指针指向第一个结点(表头结点),最后一个节点的next指针为null
    • 在已知待操作结点位置的情况下,插入和删除的时间复杂度是O(1)

二、实现

  1. 方案一:遍历整个单链表,得到链表的长度length,length/2即为单链表的中间结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function getMiddleNode($head)
{
if ($head == null || $head->next == null){
return $head;
}

$prev = $head;
$size = 0;
while($prev) {
$size++;
$prev = $prev->next;
}

$position = (int)($size/2);
while($position--) {
$head=$head->next;
}

return $head;
}
  1. 方案二:设置两个指针iji一次走一步,j一次走两步,当j到达链表尾的时候,i所指向的结点就是单链表的中间结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function getMiddleNode($head)
{
if ($head == null || $head->next == null){
return $head;
}

$p1 = $head;
$p2 = $head;

while($p2->next != null && $p2->next->next) {
$p2 = $p2->next->next
$p1 = $p1->next
}

return $p1;
}