欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

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

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

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

相关标签: leetcode