[PHP] 算法-找出两个链表的第一个公共结点的PHP实现

发布时间：2020-05-25 03:11:14 所属栏目：PHP 来源：互联网

导读：输入两个链表，找出它们的第一个公共结点1.两个单链表，有公共结点，那么必然，尾部公用2.找出链表1的长度，找出链表2的长度，长的链表减去短的链表得出一个n值3.长的链表先走n步，两个链表再同时移动4.两个链表相交点就是第一个公共结点list1 list2len1 len2

1.2.3.4.list1 list2

len1 len2
<span style="color: #0000ff">if len1 ><span style="color: #000000"> len2

n=len1-<span style="color: #000000">len2

<span style="color: #0000ff">for i=0;i<n;i++<span style="color: #000000">

list1=list1-><span style="color: #008080">next

<span style="color: #0000ff">else<span style="color: #000000">

n=len2-<span style="color: #000000">len1

<span style="color: #0000ff">for i=0;i<n;i++<span style="color: #000000">

list2=list2-><span style="color: #008080">next
<span style="color: #0000ff">while list1!=<span style="color: #0000ff">null

<span style="color: #0000ff">if list1==<span style="color: #000000">list2

<span style="color: #0000ff">return<span style="color: #000000"> list1

list1=list1-><span style="color: #008080">next<span style="color: #000000">

list2=list2-><span style="color: #008080">next

<span style="color: #0000ff">return <span style="color: #0000ff">null

data=
=->==<span style="color: #800080">$node1=<span style="color: #0000ff">new Node(1<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node1<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node1<span style="color: #000000">;
<span style="color: #800080">$node2=<span style="color: #0000ff">new Node(2<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node2<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node2<span style="color: #000000">;
<span style="color: #800080">$node3=<span style="color: #0000ff">new Node(3<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node3<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node3<span style="color: #000000">;
<span style="color: #800080">$node4=<span style="color: #0000ff">new Node(4<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node4<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node4<span style="color: #000000">;
<span style="color: #800080">$node5=<span style="color: #0000ff">new Node(5<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node5<span style="color: #000000">;

<span style="color: #800080">$node5-><span style="color: #008080">next=<span style="color: #0000ff">null<span style="color: #000000">;
<span style="color: #008000">//<span style="color: #008000">构造一个和上面有公共结点的链表

<span style="color: #800080">$linkList2=<span style="color: #0000ff">new<span style="color: #000000"> Node();

<span style="color: #800080">$linkList2-><span style="color: #008080">next=<span style="color: #0000ff">null<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$linkList2<span style="color: #000000">;
<span style="color: #800080">$node7=<span style="color: #0000ff">new Node(7<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node7<span style="color: #000000">;

<span style="color: #800080">$node7-><span style="color: #008080">next=<span style="color: #800080">$node4;<span style="color: #008000">//<span style="color: #008000">链向上面链表的第四个结点
<span style="color: #008080">var_dump(<span style="color: #800080">$linkList1<span style="color: #000000">);

<span style="color: #008080">var_dump(<span style="color: #800080">$linkList2<span style="color: #000000">);

<span style="color: #800080">$commonNode=FindFirstCommonNode(<span style="color: #800080">$linkList1,<span style="color: #800080">$linkList2<span style="color: #000000">);

<span style="color: #008080">var_dump(<span style="color: #800080">$commonNode<span style="color: #000000">);

<span style="color: #008000">//<span style="color: #008000">找第一个公共结点

<span style="color: #0000ff">function FindFirstCommonNode(<span style="color: #800080">$pHead1,<span style="color: #800080">$pHead2<span style="color: #000000">){

<span style="color: #008000">//<span style="color: #008000">链表1的长度

<span style="color: #800080">$len1=0<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$pHead1-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #0000ff">while(<span style="color: #800080">$temp!=<span style="color: #0000ff">null<span style="color: #000000">){

<span style="color: #800080">$temp=<span style="color: #800080">$temp-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #800080">$len1++<span style="color: #000000">;

}

<span style="color: #008000">//<span style="color: #008000">链表2的长度

<span style="color: #800080">$len2=0<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$pHead2-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #0000ff">while(<span style="color: #800080">$temp!=<span style="color: #0000ff">null<span style="color: #000000">){

<span style="color: #800080">$temp=<span style="color: #800080">$temp-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #800080">$len2++<span style="color: #000000">;

}

<span style="color: #800080">$list1=<span style="color: #800080">$pHead1-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #800080">$list2=<span style="color: #800080">$pHead2-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #008000">//<span style="color: #008000">长的链表先走n步

<span style="color: #0000ff">if(<span style="color: #800080">$len1 > <span style="color: #800080">$len2<span style="color: #000000">){

<span style="color: #800080">$n=<span style="color: #800080">$len1-<span style="color: #800080">$len2<span style="color: #000000">;

<span style="color: #0000ff">for(<span style="color: #800080">$i=0;<span style="color: #800080">$i<<span style="color: #800080">$n;<span style="color: #800080">$i++<span style="color: #000000">){

<span style="color: #800080">$list1=<span style="color: #800080">$list1-><span style="color: #008080">next<span style="color: #000000">;

}

}<span style="color: #0000ff">else<span style="color: #000000">{

<span style="color: #800080">$n=<span style="color: #800080">$len2-<span style="color: #800080">$len1<span style="color: #000000">;

<span style="color: #0000ff">for(<span style="color: #800080">$i=0;<span style="color: #800080">$i<<span style="color: #800080">$n;<span style="color: #800080">$i++<span style="color: #000000">){

<span style="color: #800080">$list2=<span style="color: #800080">$list2-><span style="color: #008080">next<span style="color: #000000">;

}
    }
    </span><span style="color: #008000"&gt;//</span><span style="color: #008000"&gt;两个链表长度一致，同时走，第一个相同的点就是第一个公共结点</span>
    <span style="color: #0000ff"&gt;while</span>(<span style="color: #800080"&gt;$list1</span>!=<span style="color: #0000ff"&gt;null</span><span style="color: #000000"&gt;){
            </span><span style="color: #0000ff"&gt;if</span>(<span style="color: #800080"&gt;$list1</span>==<span style="color: #800080"&gt;$list2</span><span style="color: #000000"&gt;){
                    </span><span style="color: #0000ff"&gt;return</span> <span style="color: #800080"&gt;$list1</span><span style="color: #000000"&gt;;
            }
            </span><span style="color: #800080"&gt;$list1</span>=<span style="color: #800080"&gt;$list1</span>-><span style="color: #008080"&gt;next</span><span style="color: #000000"&gt;;
            </span><span style="color: #800080"&gt;$list2</span>=<span style="color: #800080"&gt;$list2</span>-><span style="color: #008080"&gt;next</span><span style="color: #000000"&gt;;
    }
    </span><span style="color: #0000ff"&gt;return</span> <span style="color: #0000ff"&gt;null</span><span style="color: #000000"&gt;;
}

（编辑：安卓应用网）

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