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。
**分析与解答:**顺序删除
主要思路为 :
通过双重循环直接在链表上进行删除操作 。 外层循环用一个指针从第一个 结点开始遍历整个链表,然后内层循环用另外一个指针遍历其余结点 , 将与外层循环遍历到 的指针所指结点的数据域相同的结点删除。如下图所示 :
假设外层循环从 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
上一篇: 这些手机厂商太多才多艺 商场快关张了
下一篇: MYSQL之分组数据