蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】删除排序链表中的重复元素 删除排序链表中的重复元素 II

发表于 更新于 分类于 阅读次数： Valine：

Remove Duplicates from Sorted List

题目大意

删除一个有序链表中重复的元素，使得每个元素只出现一次。

解题思路

如果当前节点有后一个节点，且它们的值相等，那么当前节点指向后一个节点的下一个节点，这样就可以去掉重复的节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head
        p = head
        while p.next:
            if p.next.val == p.val:
                p.next = p.next.next
            else:
                p = p.next
        return head

Remove Duplicates from Sorted List II

题目大意

把一个有序链表中所有重复的数字全部删光，删除后不再有原先重复的那些数字。

解题思路

不同的地方是这里要删掉所有的重复项，由于链表开头可能会有重复项，被删掉的话头指针会改变，而最终却还需要返回链表的头指针。

所以需要定义一个新的节点，然后链上原链表，然后定义一个前驱指针和一个现指针，每当前驱指针指向新建的节点，现指针从下一个位置开始往下遍历，遇到相同的则继续往下，直到遇到不同项时，把前驱指针的next指向下面那个不同的元素。如果现指针遍历的第一个元素就不相同，则把前驱指针向下移一位。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        p = dummy
        temp = head
        while p.next:
            while temp.next and temp.next.val == p.next.val:
                temp = temp.next
            if temp == p.next:  # 如果p.next temp相等，说明并没有重复，两个都进一位
                p = p.next
                temp = p.next
            else:  # 如果p.next和temp不相等，说明temp已经跑到很后面了（至少大两位），所以需要将p直接指向temp.next
                p.next = temp.next
        return dummy.next

总结

两个都是链表基础题，值得反复学习