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

实现php删除链表中重复的结点

发布:smiling 来源: PHP粉丝网  添加日期:2021-10-30 11:47:39 浏览: 评论:0 

在本篇文章中,我们给大家带来了关于php删除链表中重复的结点的相关知识点内容以及相关代码,有兴趣的朋友们参考下。

删除链表中重复的结点:

定义两个指针pre和current

两个指针同时往后移动,current指针如果与后一个结点值相同,就独自往前走直到没有相等的,pre指针next直接指向current指针的后一个,把相同的都跳过

  1. pre=linkList 
  2. current=linkList 
  3. while current!=null 
  4.   if current->data==current->next->data 
  5.     value=current->data 
  6.     while value==current->next->data 
  7.       current=current->next 
  8.     pre->next=current->next 
  9.   pre=pre->next 
  10.   current=current->next 
  11. return linkList 
  12.  
  13. <?php 
  14. class Node{ 
  15.     public $data
  16.     public $next
  17.     public function __construct($data=""){ 
  18.         $this->data=$data
  19.     }   
  20. //构造一个带重复的链表 
  21. $linkList=new Node(); 
  22. $linkList->next=null; 
  23. $temp=$linkList
  24. $node1=new Node(2); 
  25. $temp->next=$node1
  26. $temp=$node1
  27. $node2=new Node(2); 
  28. $temp->next=$node2
  29. $temp=$node2
  30. $node3=new Node(3); 
  31. $temp->next=$node3
  32. $temp=$node3
  33. $node4=new Node(3); 
  34. $temp->next=$node4
  35. $temp=$node4
  36. $node5=new Node(4); 
  37. $temp->next=$node5
  38. $node5->next=null; 
  39. function deleteDuplication($pHead){ 
  40.     $pre=$pHead->next;//当前都指向第一个结点 
  41.     $current=$pHead->next;//当前结点是第一个结点 
  42.     while($current!=null){ 
  43.         //如果当前结点值和当前结点的下一个结点值相同 
  44.         if($current->next!=null && $current->data==$current->next->data){ 
  45.             //保存当前结点值 
  46.             $val=$current->data; 
  47.             //当前结点往后移直到和下一个结点值不相等 
  48.             while($current->next!=null && $val==$current->next->data){ 
  49.                 $current=$current->next; 
  50.             }   
  51.             //前一个指针next直接指向当前结点的next 
  52.             $pre->next=$current->next; 
  53.         }   
  54.         //两个指针同时后移 
  55.         $pre=$pre->next; 
  56.         $current=$current->next; 
  57.     } 
  58.     return $pHead
  59. var_dump($linkList); 
  60. $result=deleteDuplication($linkList); 
  61. var_dump($result); 
  62.  
  63. object(Node)#1 (2) { 
  64.  ["data"]=> 
  65.  string(0) "" 
  66.  ["next"]=> 
  67.  object(Node)#2 (2) { 
  68.   ["data"]=> 
  69.   int(2) 
  70.   ["next"]=> 
  71.   object(Node)#3 (2) { 
  72.    ["data"]=> 
  73.    int(2) 
  74.    ["next"]=> 
  75.    object(Node)#4 (2) { 
  76.     ["data"]=> 
  77.     int(3) 
  78.     ["next"]=> 
  79.     object(Node)#5 (2) { 
  80.      ["data"]=> 
  81.      int(3) 
  82.      ["next"]=> 
  83.      object(Node)#6 (2) { 
  84.       ["data"]=> 
  85.       int(4) 
  86.       ["next"]=> 
  87.       NULL 
  88.      } 
  89.     } 
  90.    } 
  91.   } 
  92.  } 
  93. object(Node)#1 (2) { 
  94.  ["data"]=> 
  95.  string(0) "" 
  96.  ["next"]=> 
  97.  object(Node)#2 (2) { 
  98.   ["data"]=> 
  99.   int(2) 
  100.   ["next"]=> 
  101.   object(Node)#4 (2) { 
  102.    ["data"]=> 
  103.    int(3) 
  104.    ["next"]=> 
  105.    object(Node)#6 (2) { 
  106.     ["data"]=> 
  107.     int(4) 
  108.     ["next"]=> 
  109.     NULL 
  110.    } 
  111.   } 
  112.  } 
  113. }

Tags: php删除链表 php删除重复结点

分享到: