剑指offer——python【第56题】删除链表中的重复节点

时间：2022-04-20 05:56:54

题目描述

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

思路

有好几种方法，先讲两种，不递归的，第三种递归，暂时不会。。

第一种，简单粗暴，把链表所有元素都放到一个列表里，然后把列表中数量大于1的元素删除，再把这些元素串成链表

第二种，设定一个新的头结点（0），然后定两个指针，一个指针初始节点在原来的头结点，另一个指针在0结点，然后让0结点作为头结点的根节点；第一个指针去遍历链表，当遇到重复结点的时候，就跳过，跳到后面的非重复节点上去，第二个指针就始终停在重复节点的前一个节点（也就是非重复节点）上。

详细描述一下，以题目描述中的链表为例，

1、一开始指针一在1节点上，指针二在0节点上，然后指针一、二分别向后遍历，当遇到重复节点时，此时指针一是3节点，指针二是2节点，指针二不会动，指针一会跳到指针4上去，同样遇到了重复节点4，指针一会跳到节点5上去，然后再把指针一的结点5和指针二的节点2相连，这样就删除了重复节点

解答

方法1

class Solution:

    def deleteDuplication(self, pHead):

        # write code here

        res = []

        while pHead:

            res.append(pHead.val)

            pHead = pHead.next

        res = list(filter(lambda c: res.count(c) == 1, res))

        newHead = ListNode(0)

        pre = newHead

        for i in res:

            node = ListNode(i)

            pre.next = node

            pre = pre.next

        return newHead.next

方法2

class Solution:

    def deleteDuplication(self, pHead):

        first = ListNode(0)

        first.next = pHead

        pre = pHead

        last = first

        while pre and pre.next:

            if pre.val != pre.next.val:

                pre = pre.next

                last = last.next

            else:

                val = pre.val

                while pre and pre.val == val:

                    pre = pre.next

                last.next = pre

        return first.next

相关文章