三指针 | #删除链表中重复的结点#

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用于判断后续元素是否重复

1. 三指针，b是可能的重复元素起点，c是可能的重复元素终点
2. 状态机，三个指针的移动方式在是否已经找到重复序列时是不一样的
3. 序列pad，老生常谈，避免特殊长度序列的复杂分支