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

一、总结

二、php实现删除链表中重复的节点

题目描述：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

三、总结

代码一：

 1 <?php
 2 /*class ListNode{
 3     var $val;
 4     var $next = NULL;
 5     function __construct($x){
 6         $this->val = $x;
 7     }
 8 }*/
 9 function deleteDuplication($pHead)
10 {
11     if($pHead==null){ //各种情况判断
12         return null;
13     }
14     if($pHead!=null&&$pHead->next==null){
15         return $pHead;
16     }
17     $cur = $pHead;
18     if($pHead->next->val==$pHead->val){
19         $cur = $pHead->next->next;
20         while($cur!=null&&$cur->val==$pHead->val){
21             $cur = $cur->next;
22         }
23         return deleteDuplication($cur);
24     }else{
25         $cur = $pHead->next;
26         $pHead->next = deleteDuplication($cur);
27         return $pHead;
28     }
29 }

代码二：没ac

 1 <?php
 2 /*class ListNode{
 3     var $val;
 4     var $next = NULL;
 5     function __construct($x){
 6         $this->val = $x;
 7     }
 8 }*/
 9 function deleteDuplication($pHead)
10 {
11     $head=new ListNode(-1);
12     $ans=$head;
13     $head->next=$pHead;
14     while($head){
15         if($head->next&&$head->next->next){
16             $l1=$head->next;
17             $l2=$l1->next;
18             while($l1->val==$l2->val){
19                 $head->next=$l2->next;
20                 if($l2->next) $l2=$l2->next;
21                 else break;
22             }
23             $head=$head->next;
24         }
25     }
26     return $ans->next;
27 }

代码三：

 1 public static ListNode deleteDuplication(ListNode pHead) {
 2          
 3         ListNode first = new ListNode(-1);//设置一个trick
 4  
 5         first.next = pHead;
 6  
 7         ListNode p = pHead;
 8         ListNode last = first;
 9         while (p != null && p.next != null) {
10             if (p.val == p.next.val) {
11                 int val = p.val;
12                 while (p!= null&&p.val == val)
13                     p = p.next;
14                 last.next = p;
15             } else {
16                 last = p;
17                 p = p.next;
18             }
19         }
20         return first.next;
21     }

代码四：

 1 递归
 2 class Solution {
 3 public:
 4     ListNode* deleteDuplication(ListNode* pHead)
 5     {
 6         if (pHead==NULL)
 7             return NULL;
 8         if (pHead!=NULL && pHead->next==NULL)
 9             return pHead;
10                  
11         ListNode* current;
12          
13         if ( pHead->next->val==pHead->val){
14             current=pHead->next->next;
15             while (current != NULL && current->val==pHead->val)
16                 current=current->next;
17             return deleteDuplication(current);                     
18         }
19          
20         else {
21             current=pHead->next;
22             pHead->next=deleteDuplication(current);
23             return pHead;
24         }    
25     }
26 };