三指针 | #删除链表中重复的结点#
删除链表中重复的结点
https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=265&tqId=39270&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26pageSize%3D50%26search%3D%26tpId%3D13%26type%3D265&difficulty=undefined&judgeStatus=undefined&tags=&title=
class Solution:
def deleteDuplication(self , pHead: ListNode) -> ListNode:
# padding data避免特殊情况的复杂处理
pad_pHead = ListNode(-1)
pad_pHead.next = pHead
pad_pHead1 = ListNode(-2)
pad_pHead1.next = pad_pHead
pad_pHead2 = ListNode(-3)
pad_pHead2.next = pad_pHead1
cur_node = pad_pHead2
pal1_node = cur_node.next
pal2_node = pal1_node.next
find_dup = 0 # 设置一个状态，表示当前是否已找到重复元素
while pal2_node:
if pal1_node.val == pal2_node.val: # 如果pal1和pal2相等，则向右移动pal2
find_dup = 1 # 找到重复元素
if not pal2_node.next: # pal2为最终节点，迭代终止
cur_node.next = None
break
else: # cur_node和pal1_node不动，pal2右移，进入下一次迭代
pal2_node = pal2_node.next
continue
## 如果pal1和pal2不等（上面的continue和break保证了相等时不会进入），进入以下代码
if find_dup:
# 之前的迭代已经找到重复元素，所以cur_node的next要更新到pal2_node，pal1和pal2相应更新
cur_node.next = pal2_node
pal1_node = pal2_node
pal2_node = pal2_node.next
else:
# 之前的迭代未找到重复元素，所以cur，pal1和pal2相应往后移动一个即可
cur_node = cur_node.next
pal1_node = pal1_node.next
pal2_node = pal2_node.next # 不要用cur_node = pal1_node，浅拷贝会同时改变两者
find_dup = 0
pad_pHead2 = pad_pHead2.next.next.next # 去pad
return pad_pHead2
基本思路是一个指针a指向检查点，另外两个b、c用于判断后续元素是否重复
- 三指针，b是可能的重复元素起点，c是可能的重复元素终点
- 状态机，三个指针的移动方式在是否已经找到重复序列时是不一样的
- 序列pad，老生常谈，避免特殊长度序列的复杂分支
