WechatIMG608.jpeg

题目描述

leetcode 第82题：删除排序链表中的重复元素 II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例：

linkedlist1.jpeg
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

解题方法一

栈
原址题解

• 解题思路

使用栈stack来存储链表中的数字
定义变量pop来表示每次出栈数字，初始为None
遍历链表head
若当前节点数字head.val存在于栈中，更新出栈数字
若当前节点数字不等于出栈数字，将节点数字压栈
遍历完成，此时栈中都是不重复的数字，再将栈转为链表返回即可

• 复杂度

时间复杂度：O(n)，n为链表的长度
空间复杂度：O(n)，n为栈的大小

• 代码实现

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head: return head
        stack = []
        pop = None
        while head:
            if head.val in stack:
                pop = stack.pop()
            if head.val!=pop:
                stack.append(head.val)
            head = head.next
        dummy = ListNode()
        cur = dummy
        for v in stack:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

class Solution {
    function deleteDuplicates($head) {
        if(!$head) return $head;
        $stack = [];
        $pop = null;
        while($head){
            if(in_array($head->val,$stack)){
                $pop = array_pop($stack);
            }
            if($pop!==$head->val){
                array_push($stack,$head->val);
            }
            $head = $head->next;
        }
        $dummy = new ListNode();
        $cur = $dummy;
        foreach($stack as $v){
            $cur->next = new ListNode($v);
            $cur = $cur->next;
        }
        return $dummy->next;
    }
}

解题方法二

链表
参照题解

• 解题思路

由于链表head的头节点可能会被删除
添加一个哑节点指向链表的头节点，得到新的链表dummy
使用指针cur表示当前节点开始遍历链表
如果cur.next.val等于cur.next.next.val
记下cur.next.val为temp，指针后移，将等于temp的节点删除
反之将cur指向cur.next
遍历完成，此时链表中剩余哑节点和不重复的节点
跳过哑节点，直接返回dummy.next即可

• 复杂度

时间复杂度：O(n)，n为链表的长度
空间复杂度：O(1)

• 代码实现

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head: return head
        dummy = ListNode(0,head)
        cur = dummy
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                temp = cur.next.val
                while cur.next and temp==cur.next.val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

class Solution {
    function deleteDuplicates($head) {
        if(!$head) return $head;
        $dummy = new ListNode(0,$head);
        $cur = $dummy;   
        while($cur->next && $cur->next->next){
            if($cur->next->val == $cur->next->next->val){
                $temp = $cur->next->val;
                while($cur->next && $temp==$cur->next->val){
                    $cur->next = $cur->next->next;
                }
            }else{
                $cur = $cur->next;
            }
        }
        return $dummy->next;
    }
}