当前位置:首页 > PHP教程 > php高级应用 > 列表

PHP学习之查找两个链表的第一个公共结点

发布:smiling 来源: PHP粉丝网  添加日期:2020-04-04 22:10:43 浏览: 评论:0 

本篇文章小编将带大家学习用PHP实现查找两个链表的第一个公共结点,具有一定的参考价值,感兴趣的朋友可以看看,希望对你有所帮助。

输入两个链表,找出它们的第一个公共结点

1.两个单链表,有公共结点,那么必然,尾部公用

2.找出链表1的长度,找出链表2的长度,长的链表减去短的链表得出一个n值

3.长的链表先走n步,两个链表再同时移动

4.两个链表相交点就是第一个公共结点

  1. list1 list2 
  2.  
  3. len1 len2 
  4.  
  5.   
  6.  
  7. if len1 > len2 
  8.  
  9.     n=len1-len2 
  10.  
  11.     for i=0;i<n;i++ 
  12.  
  13.         list1=list1->next 
  14.  
  15. else 
  16.  
  17.     n=len2-len1 
  18.  
  19.     for i=0;i<n;i++ 
  20.  
  21.         list2=list2->next 
  22.  
  23.   
  24.  
  25. while list1!=null 
  26.  
  27.     if list1==list2  
  28.  
  29.         return list1 
  30.  
  31.     list1=list1->next 
  32.  
  33.     list2=list2->next 
  34.  
  35. return null 
  36.  
  37. <?php 
  38.  
  39. class Node{ 
  40.  
  41.         public $data
  42.  
  43.         public $next
  44.  
  45.         public function __construct($data=""){ 
  46.  
  47.                 $this->data=$data
  48.  
  49.         }    
  50.  
  51.  
  52. //构造一个链表 
  53.  
  54. $linkList1=new Node(); 
  55.  
  56. $linkList1->next=null; 
  57.  
  58. $temp=$linkList1 
  59.  
  60. $node1=new Node(1); 
  61.  
  62. $temp->next=$node1
  63.  
  64. $temp=$node1 
  65.  
  66. $node2=new Node(2); 
  67.  
  68. $temp->next=$node2
  69.  
  70. $temp=$node2
  71.  
  72. $node3=new Node(3); 
  73.  
  74. $temp->next=$node3
  75.  
  76. $temp=$node3 
  77.  
  78. $node4=new Node(4); 
  79.  
  80. $temp->next=$node4
  81.  
  82. $temp=$node4; 
  83.  
  84. $node5=new Node(5); 
  85.  
  86. $temp->next=$node5
  87.  
  88. $node5->next=null; 
  89.  
  90. //构造一个和上面有公共结点的链表 
  91.  
  92. $linkList2=new Node(); 
  93.  
  94. $linkList2->next=null; 
  95.  
  96. $temp=$linkList2
  97.  
  98. $node7=new Node(7); 
  99.  
  100. $temp->next=$node7
  101.  
  102. $node7->next=$node4;//链向上面链表的第四个结点   
  103.  
  104. var_dump($linkList1); 
  105.  
  106. var_dump($linkList2); 
  107.  
  108. $commonNode=FindFirstCommonNode($linkList1,$linkList2); 
  109.  
  110. var_dump($commonNode); 
  111.  
  112. //找第一个公共结点 
  113.  
  114. function FindFirstCommonNode($pHead1$pHead2){ 
  115.  
  116.         //链表1的长度 
  117.  
  118.         $len1=0; 
  119.  
  120.         $temp=$pHead1->next; 
  121.  
  122.         while($temp!=null){ 
  123.  
  124.                 $temp=$temp->next; 
  125.  
  126.                 $len1++; 
  127.  
  128.         } 
  129.  
  130.         //链表2的长度 
  131.  
  132.         $len2=0; 
  133.  
  134.         $temp=$pHead2->next; 
  135.  
  136.         while($temp!=null){ 
  137.  
  138.                 $temp=$temp->next; 
  139.  
  140.                 $len2++; 
  141.  
  142.         } 
  143.  
  144.         $list1=$pHead1->next; 
  145.  
  146.         $list2=$pHead2->next; 
  147.  
  148.         //长的链表先走n步 
  149.  
  150.         if($len1 > $len2){ 
  151.  
  152.                 $n=$len1-$len2
  153.  
  154.                 for($i=0;$i<$n;$i++){ 
  155.  
  156.                         $list1=$list1->next; 
  157.  
  158.                 } 
  159.  
  160.         }else
  161.  
  162.                 $n=$len2-$len1
  163.  
  164.                 for($i=0;$i<$n;$i++){ 
  165.  
  166.                         $list2=$list2->next; 
  167.  
  168.                 } 
  169.  
  170.   
  171.  
  172.         } 
  173.  
  174.         //两个链表长度一致,同时走,第一个相同的点就是第一个公共结点 
  175.  
  176.         while($list1!=null){ 
  177.  
  178.                 if($list1==$list2){ 
  179.  
  180.                         return $list1
  181.  
  182.                 } 
  183.  
  184.                 $list1=$list1->next; 
  185.  
  186.                 $list2=$list2->next; 
  187.  
  188.         } 
  189.  
  190.         return null; 
  191.  
  192. } 
  193.  
  194. object(Node)#1 (2) { 
  195.  
  196.   ["data"]=> 
  197.  
  198.   string(0) "" 
  199.  
  200.   ["next"]=> 
  201.  
  202.   object(Node)#2 (2) { 
  203.  
  204.     ["data"]=> 
  205.  
  206.     int(1) 
  207.  
  208.     ["next"]=> 
  209.  
  210.     object(Node)#3 (2) { 
  211.  
  212.       ["data"]=> 
  213.  
  214.       int(2) 
  215.  
  216.       ["next"]=> 
  217.  
  218.       object(Node)#4 (2) { 
  219.  
  220.         ["data"]=> 
  221.  
  222.         int(3) 
  223.  
  224.         ["next"]=> 
  225.  
  226.         object(Node)#5 (2) { 
  227.  
  228.           ["data"]=> 
  229.  
  230.           int(4) 
  231.  
  232.           ["next"]=> 
  233.  
  234.           object(Node)#6 (2) { 
  235.  
  236.             ["data"]=> 
  237.  
  238.             int(5) 
  239.  
  240.             ["next"]=> 
  241.  
  242.             NULL 
  243.  
  244.           } 
  245.  
  246.         } 
  247.  
  248.       } 
  249.  
  250.     } 
  251.  
  252.   } 
  253.  
  254.  
  255. object(Node)#7 (2) { 
  256.  
  257.   ["data"]=> 
  258.  
  259.   string(0) "" 
  260.  
  261.   ["next"]=> 
  262.  
  263.   object(Node)#8 (2) { 
  264.  
  265.     ["data"]=> 
  266.  
  267.     int(7) 
  268.  
  269.     ["next"]=> 
  270.  
  271.     object(Node)#5 (2) { 
  272.  
  273.       ["data"]=> 
  274.  
  275.       int(4) 
  276.  
  277.       ["next"]=> 
  278.  
  279.       object(Node)#6 (2) { 
  280.  
  281.         ["data"]=> 
  282.  
  283.         int(5) 
  284.  
  285.         ["next"]=> 
  286.  
  287.         NULL 
  288.  
  289.       } 
  290.  
  291.     } 
  292.  
  293.   } 
  294.  
  295.  
  296. object(Node)#5 (2) { 
  297.  
  298.   ["data"]=> 
  299.  
  300.   int(4) 
  301.  
  302.   ["next"]=> 
  303.  
  304.   object(Node)#6 (2) { 
  305.  
  306.     ["data"]=> 
  307.  
  308.     int(5) 
  309.  
  310.     ["next"]=> 
  311.  
  312.     NULL 
  313.  
  314.   } 
  315.  
  316. }

Tags: PHP查找两个链表

分享到: