删除链表中重复结点

发表于 | 分类于 | 次

###题目

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

解题思路

递归。

代码实现

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
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#python2, 递归， 时间41ms，内存：5760k
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead is None or pHead.next is None:
            #首先判断是否为空，或是否只有一个结点。
            return pHead
        else:
            if pHead.val != pHead.next.val:
                 #如果当前结点值不等于下一结点值，则该结点保留并返回
                pHead.next = self.deleteDuplication(pHead.next)
            else:
                  #否则从下一个结点开始寻找下一个不重复的结点。找到后返回，并判断是否与当前结点相等。
                temp = self.deleteDuplication(pHead.next.next)
                if temp is not None and pHead.val == temp.val:
                    pHead = None
                else :
                    pHead = temp
            return pHead