快乐的LeetCode --- 82. 删除排序链表中的重复元素 II (删除链表中重复的结点)

梦里梦外; 2023-07-24 09:25 11阅读 0赞

**题目描述：**

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

**示例 1:**

输入: 1->2->3->3->4->4->5
    输出: 1->2->5

**示例 2:**

输入: 1->1->1->2->3
    输出: 2->3

--------------------

**解题思路1:**

来源于：[Forlogen][]

首先新建结点拼接到链表头部，设置指针`p`指向新结点，`cur`指向`head`判断`cur.val`和`cur.next.val`的关系：

*  如果 `cur.val == cur.next.val`，则执行`cur = cur.next`，直到`cur`指向的元素不等于当前元素
 *  如果 `cur.val != cur.next.val`，则执行`cur = cur.next, p = p.next`，继续往后判断，直到`cur.next == None`
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]

--------------------

**代码1：**

class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            newhead = ListNode(-1)
            p = newhead
            p.next = head
            cur = head
            while cur and cur.next:
                if cur.val != cur.next.val:
                    p = p.next
                    cur = cur.next
                else:
                    val = cur.val
                    while cur and cur.val == val:
                        cur = cur.next
                    p.next = cur
            return newhead.next

另一种写法：

class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            temp=pre=ListNode(-1)   
            temp.next=head
            while head and head.next: #判断当前和下一个，若只有一个了就结束，因为不重
                if head.val==head.next.val:
                    while head and head.next and head.val==head.next.val:
                        head=head.next
                    head=head.next
                    pre.next=head  
                else:
                    head=head.next
                    pre=pre.next
            return temp.next

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii][https_leetcode-cn.com_problems_remove-duplicates-from-sorted-list-ii]

--------------------

**同类题目：**

\[1\]. [面试题18. 删除链表的节点][18.]  
\[2\]. [237. 删除链表中的节点][237.]  
\[3\]. [876. 链表的中间结点][876.]  
\[4\]. [83. 删除排序链表中的重复元素][83.]

[Forlogen]: https://blog.csdn.net/Forlogen/article/details/105098774
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/38fa3b2d7d9b4cd9bb1b7bf6c3e30020.png
[https_leetcode-cn.com_problems_remove-duplicates-from-sorted-list-ii]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
[18.]: https://blog.csdn.net/weixin_43283397/article/details/105438866
[237.]: https://blog.csdn.net/weixin_43283397/article/details/105442282
[876.]: https://blog.csdn.net/weixin_43283397/article/details/105054398
[83.]: https://blog.csdn.net/weixin_43283397/article/details/105442918