【LeetCode 83】删除排序链表中的重复元素 VS. 【剑指offer】删除链表中重复元素

【LeetCode 83】删除排序链表中的重复元素 VS. 【剑指offer】删除链表中重复元素

题目区别：

LeetCode 83 题和 剑指offer中的这一题类似但是题目要求不同。区别如下：

LeetCode中，是把重复元素删除到保留一个为止如：[1, 1, 1, 2] => [1, 2]剑指offer中，是要把相同的元素全部删除，一个不留如：[1, 1, 1, 2] => [2]

1. LeetCode 83 （保留一个重复元素）

题目：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1: 输入: 1->1->2 输出: 1->2

思路：只需要一个指针，如果没有发生重复，则指针每次后移一步，如果发生重复，则指针跳过重复元素。

Python代码

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: """ 【单指针】 如果用 No. 26“删除排序数组中的重复元素”的方法，会导致后面还留着没用的尾巴 [1 1 1 2] p 此时 p.val == p.next.val ，p.next = p.next.next 也就是 跳过一个中间的节点，但是 p 指针并没有移动！！！ [1 1 1 2] | | -------- p 此时 p.val == p.next.val ，p.next = p.next.next ,但是 p 指针并没有移动！！！ [1 1 1 2] | | ----------- p 此时 p.val != p.next.val ，p = p.next 此时p指针才移动 ！！！ [1 1 1 2] | | ------------ p 此时 p.next is None 所以结束循环 """ # print(head.val) if not head: return None p = head while(p and p.next): if p.val == p.next.val: p.next = p.next.next # 这个时候 p 指针并没有后移，而是箭头不断跳过中间重复的节点 else: # 只有当前后两个值不想等的时候，才能 p 往后移动 p = p.next return

=====================================================================

2. 剑指offer （不保留重复元素）

题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

思路：这里对发生重复的节点一个不留，会更难一些。需要两个指针，第一个指针停留在发生重复段的前面一个节点，第二个指针停留在发生重复段的后面一个节点，然后，第一个指针跳过中间的重复段，直接连接到第二个指针。这样就完成了对所有重复节点的删除。

Python代码

# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def deleteDuplication(self, pHead): if (not pHead) or (not pHead.next): return pHead # 自己构建辅助哨兵节点，方便处理头结点 head = ListNode(None) # 注意需要带一个参数 None ！！！ head.next = pHead pre = head cur = pHead while(cur): if (cur.next) and (cur.val == cur.next.val): # 相同的节点一直前进 while (cur.next) and (cur.val == cur.next.val): cur = cur.next # 退出循环时，cur指向重复值，cur.next指向第一个不重复的值 cur = cur.next # cur继续前进 pre.next = cur # pre 连接新的节点 else: pre = cur cur = cur.next return head.next

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。