[剑指Offer]删除链表中重复的节点

链表的基础知识+Python实现四种链表

题目描述

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

解题思路

  1. 题目看起来挺简单的,其实做起来坑很多,需要用一点小技巧;
  2. 坑:需要完全去掉重复的节点而不是保留一个、需要返回链表头指针;
  3. 特殊输入测试:空链表、首节点重复、连续多个重复、完全重复的链表。

代码

Python(2.7.3)

解法一:加新的节点

  • 在原链表之前链一个节点pre_head,用它的.next属性返回原列表去重后的链表头指针;
  • 使用两个指针curpre,分别指当前判断的节点和当前节点的前一个节点;
  • 因为可能会出现连续重复的节点值,所以需要循环内再套循环判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
pre_head = ListNode(0)
pre_head.next = pHead
pre = pre_head
cur = pHead
while cur is not None:
if cur.next is not None and cur.next.val == cur.val:
tmp = cur.next
while tmp is not None and tmp.val == cur.val:
tmp = tmp.next
pre.next = tmp
cur = tmp
else:
pre = cur
cur = cur.next
return pre_head.next

运行时间:30ms
占用内存:5828k

解法二:递归

采用递归思想将满足一定条件的后半段链表递归地调用函数本身。详见代码注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# -*- 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 is None or pHead.next is None:
return pHead
real_head = pHead # real_head为原链表去重复节点之后的链表头指针
aft = pHead.next # aft为原链表的第二个节点
if aft.val != real_head.val:
# 若前两个节点不同,则real_head就是pHead。对后面的子链表递归调用
real_head.next = self.deleteDuplication(aft)
else:
# 若前两个节点相同,则需找出真正的链表头节点
tmp = aft
# 循环向后找到与pHead不同的那个节点
while tmp.val == real_head.val and tmp.next is not None:
tmp = tmp.next
if tmp.val != real_head.val:
# 则后半段子链表的链表头为原链表的链表头(有可能再次递归,但不影响)
real_head = self.deleteDuplication(tmp)
else:
# 若整个链表完全重复则返回None
return None
return real_head

运行时间:47ms
占用内存:5856k

参考

https://www.nowcoder.com/profile/800862/codeBookDetail?submissionId=12139833
https://www.nowcoder.com/profile/6935185/codeBookDetail?submissionId=12608448