剑指 删除链表重复节点

使用一个栈，和一个数组辅助实现。遍历一次链表将不重复的节点放入栈中，其中判断不重复使用duplicate,然后通过栈来生成链表返回 时间O(n) 空间O(n)

# -*- 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 or pHead.next==None:
            return pHead
        l=pHead
        stack=[]
        duplicate=[]
        r=result=ListNode(0)
        while l!=None:
            if len(stack)==0 or l.val!=stack[-1].val :
                if l.val not in duplicate:
                    stack.append(l)
            else:

                stack=stack[:-1]
                duplicate.append(l.val)
            l=l.next
        print(duplicate)
        print(stack)
        for node in stack:
            r.next=node
            r=r.next
        r.next=None
        return result.next

先遍历一遍，把链表中重复的节点都放到数组中，然后在进行遍历，设置pre 和 cur 节点，当遇到重复的节点了就删除它。pre.next=cur.next

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead==None or pHead.next==None:
            return pHead
        l=cur=pHead
        result=pre=ListNode(0)
        pre.next=pHead
        st=set()
        while cur.next!=None:
            if cur.val==cur.next.val:
                st.add(cur.val)
            cur=cur.next
        while l!=None:
            if l.val in st:
                pre.next=l.next
                l=pre.next
            else:
                l=l.next
                pre=pre.next

        return result.next 

第二种方法的改造，当遇到重复节点，循环找到直到不是重复节点的位置在结束。

# -*- 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 or pHead.next==None:
            return pHead
        l=cur=pHead
        result=pre=ListNode(0)
        pre.next=pHead
        st=set()
        while cur.next!=None:
            if cur.val==cur.next.val:
                st.add(cur.val)
            cur=cur.next
        while l!=None:
            if l.val in st:
                while  l!=None and l.val in st:
                    l=l.next
                pre.next=l
            else:
                l=l.next
                pre=pre.next


        return result.next 

直接删除方法，判断节点是否与下一个相同，相同的话继续向后寻找直到没有相同的节点，将pre.next连接过去，当和下一个节点不相同的时候，pre与l指针后移。

# -*- 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 or pHead.next==None:
            return pHead
        l=cur=pHead
        result=pre=ListNode(0)
        pre.next=pHead


        while  l!=None and l.next!=None :
            if l.val==l.next.val:
                while  l!=None and l.next!=None and l.val==l.next.val:
                    l=l.next
                l=l.next
                pre.next=l


            else:
                l=l.next
                pre=pre.next


        return result.next 

递归方法 当头节点与下一个节点相等，那就找到不相等的节点，递归函数。如果不相等，那头结点的next指向递归函数处理除去头节点的剩下部分。

# -*- 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 or pHead.next==None:
            return pHead



        if pHead.val==pHead.next.val:
            cur=pHead.next
            while cur!=None and cur.val==pHead.val:
                cur=cur.next
            return self.deleteDuplication(cur)

        else:
            pHead.next=self.deleteDuplication(pHead.next)
            return pHead