82.remove-duplicates-from-sorted-list-ii

Statement

简体中文English

Metadata

• Link: 删除排序链表中的重复元素 II
• Difficulty: Medium
• Tag: 链表 双指针

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

 

示例 1：

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

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

 

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

Metadata

• Link: Remove Duplicates from Sorted List II
• Difficulty: Medium
• Tag: Linked List Two Pointers

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

 

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

 

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Solution

Python 3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        pre = 1000
        cnt = 1
        res = ListNode()
        cur = res
        while head:
            if head.val == pre:
                cnt += 1
            else:
                if cnt == 1 and pre != 1000:
                    cur.next = ListNode()
                    cur = cur.next
                    cur.val = pre
                pre = head.val
                cnt = 1

            head = head.next

        if cnt == 1 and pre != 1000:
            cur.next = ListNode()
            cur = cur.next
            cur.val = pre

        return res.next

---

最后更新: October 11, 2023