面试题18：删除链表中重复的节点

题目描述

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

知识点

链表

Qiang的思路

对于这个问题，我们可以设置三个指针，一个遍历链表，判断每一个位置是不是重复，另一个指向第一个指针的上一个元素，目的是当第一个指针指向的元素和其后的元素重复的时候，我们直接让第二个指针指向下一个不重复的节点，这样就把中间的节点全部删除掉了。显然，下一个不重复的节点就需要第三个指针指向，这是因为该节点从第一个节点开始，往后遍历判断其后有没有重复的，这样就会停在第一个不重复的节点上了。

按照这个思路，我们设置了三个指针，当第一个指针遍历时，起始位置应该第一个节点，但由于第二个指针需要有指向，所以我们将起始位置设置为第二个节点，这样就无法考虑第一个节点了，显然就有一个问题，如果当第一个节点就是重复的时候，我们的策略需要将其单独考虑。但是实际上并不需要，我们可以增加一个头节点，将该头结点取值设置为空，然后从真实的第一个节点开始遍历，就能不用考虑这种特殊情况了。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        result=ListNode(None)
        result.next=pHead
        before=result
        while pHead!=None:
            after=pHead.next
            flag=False
            while after!=None and pHead.val==after.val:
                flag=True
                after=after.next
            if flag==True:
                before.next=after
            else:
                before=before.next
            pHead=after
        return result.next

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。