python实现从无序的链表中删除重复项

题目描述:
给定一个没有排序的链表，去掉其重复项， 并保留原顺序，例如链表 1 >3 >1一>5一>5->7,
去掉重复项后变为 l一>3一>5->7。
**分析与解答:**顺序删除
主要思路为 :
通过双重循环直接在链表上进行删除操作 。 外层循环用一个指针从第一个 结点开始遍历整个链表，然后内层循环用另外一个指针遍历其余结点 ， 将与外层循环遍历到 的指针所指结点的数据域相同的结点删除。如下图所示 :

假设外层循环从 outerCur 开始遍历，当内层循环指针 innerCur 遍历到上图实线所示 的位 置( outerCur.data= =innerCur.data)时 ， 需要把 innerCur 指向的结点删除。具体步骤如 下:
Cl)用 tmp记录待删除的结点的地址。
(2)为了能够在删除 tmp 结点后继续遍历链表中其余的结点，使 innerCur指向它的后继 结点 :由ierCur=innerCur.next。
(3) 从链表中删除tmp结点。 实现代码如下:

class LNode:
    def __init__(self,x):
        self.data=x
        self.next=None
def removeDup(head):
    if head==None or head.next==None:
        return
    outcur=head
    incur=None
    incurpre=None
    while outcur!=None:
        incur=outcur.next
        incurpre=outcur
        while incur!=None:
            if incur.data==outcur.data:
                incurpre.next=incur.next
                incur=incur.next
            else:
                incurpre=incur
                incur=incur.next
        outcur=outcur.next
if __name__=='__main__':
    i=1
    head=LNode(0)
    head.next=None
    temp=None
    cur=head
    while i<7:
        tmp=LNode(0)
        if i%2==0:
            tmp.data=i+1
        elif i%3==0:
            tmp.data=i-2
        else:
            tmp.data=i
        tmp.next=None
        cur.next=tmp
        cur=tmp
        i+=1
    print('删除重复节点前：')
    cur=head.next
    while cur!=None:
        print(cur.data)
        cur=cur.next
    removeDup(head)
    print('删除节点后：')
    cur=head.next
    while cur!=None:
        print(cur.data)
        cur=cur.next

输出：
删除重复节点前：
1
3
1
5
5
7
删除节点后：
1
3
5
7

本文地址：https://blog.csdn.net/weixin_42813521/article/details/107648297