题目区别：
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 = None
class 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 head
=====================================================================
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 = None
class 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
京公网安备 11010502036488号