82.md

✏️基础刷题之(82. Remove Duplicates from Sorted List II)

. 2020-01-14 吴亲库里 库里的深夜食堂

✏️描述

给定一个有序的链表，删除具有重复的节点，返回只出现一次的节点

---

✏️题目实例

​

---

✏️题目分析

这个问题在于如果想 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;
    }

联系

​