剑指offer刷题笔记56（python）

题目描述

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

思路1

利用递归，如果当前节点是重复节点时，越过与当前节点相同的节点，找到第一个与当前节点的值不相同的节点，从第一个与当前结点不同的结点开始递归（重复的节点一个都不留）。如果当前节点不是重复节点，保留当前节点，从下一个节点开始递归。

代码1

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 递归 def deleteDuplication(self, pHead): # write code here if pHead == None: return None if pHead.next == None: return pHead if pHead.val != pHead.next.val: pHead.next = self.deleteDuplication(pHead.next) return pHead # 后面的节点递归结束后，返回pHead即可 else: tempNode = pHead while tempNode and tempNode.val == pHead.val: tempNode = tempNode.next return self.deleteDuplication(tempNode) # 重复节点都不留，不保留pHead，直接返回下一个不同节点的递归结点。

思路2

不用递归，用循环，当碰见一个重复的节点是，通过循环找到第一个不同的节点，这时需要一个记录当前节点之前情况的指针。

代码2

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteDuplication(self, pHead): # write code here first = ListNode(-1) # 为了避免重复，在链表开始之前新建一个头结点。 first.next = pHead curr = pHead # 作为遍历链表的指针 pre = first # 记录不重复节点之前的最后信息 while curr and curr.next: if curr.val != curr.next.val: # 当前节点不重复，继续往下走 curr = curr.next pre = pre.next else: # 如果重复，找到不重复节点为止。 val = curr.val while curr and curr.val == val: curr = curr.next pre.next = curr # 这里直接令pre.next等于第一个与当前元素不重复的节点即可， # 不用管这个节点也是重复节点，因为pre一定不重复，且被固定了下来， # 是不变的，如果这个节点也是重复节点，pre.next会再次更新。 return first.next