leetCode ✏基础刷题之(82. Remove Duplicates from Sorted List II)
.
✏描述
给定一个有序的链表，删除具有重复的节点，返回只出现一次的节点
✏题目实例
✏题目分析
这个问题在于如果想 demo2 这种情况，是可能出现连头结点都删除的情况的。也就是说我们需要创建一个可控的前驱节点，我们才能控制接下来的节点。直白点地说就是，你要删除当前这个节点，那么你肯定是控制上一个节点的 next 指针指向当前节点的 next 指针。因此定义一个前驱节点和现节点。现节点往下走，只要发现相同的节点，那么继续 next,直到遇到不同的值，那么就把前驱节点的 next 指针指向现节点的 next 指针即可。如果现节点遍历的第一个节点就不相同，那么直接把前驱指针指向下一位即可。
✏最终实现代码
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function deleteDuplicates($head) {
if(!$head || !$head->next) return $head;
$dummy=new ListNode(-1);
$pre=$dummy;
$dummy->next=$head;
while($pre->next){
$node=$pre->next;
while($node->next && $node->next->val ==$node->val){
$node=$node->next;
}
if($node !=$pre->next) $pre->next=$node->next;
else $pre=$pre->next;
}
return $dummy->next;
}
}
递归实现
/**
* @param ListNode $head
* @return ListNode
*/
function deleteDuplicates($head) {
if(!$head) return $head;
if($head->next && $head->val==$head->next->val){
while($head->next && $head->val==$head->next->val){
$head=$head->next;
}
return $this->deleteDuplicates($head->next);
}
$head->next=$this->deleteDuplicates($head->next);
return $head;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)