【week08】作业

用户头像
chengjing
关注
发布于: 2020 年 07 月 27 日

作业1:

#链表节点类
class list_node():
def __init__(self, val=None):
self.val = val
self.next = None
def __repr__(self):
return self.val
def __str__(self):
return self.val
#链表类
class linkedlist():
def __init__(self):
self.begin = list_node(None)
self.end = self.begin
def append(self, node):
self.end.next= node
node.next = None
self.end = node
def all(self):
n = self.begin
while n.next != None:
yield n.next
n = n.next
#初始化节点
nodes={'a':list_node('a'),'b':list_node('b'),'d':list_node('d'),'e':list_node('e'),'f':list_node('f'), 'x':list_node('x'),'y':list_node('y'),'z':list_node('z')}
#链表a,b,x,y,z
llist1 = linkedlist()
llist1.append(nodes['a'])
llist1.append(nodes['b'])
llist1.append(nodes['x'])
llist1.append(nodes['y'])
llist1.append(nodes['z'])
#链表d,e,f,x,y,z
llist2 = linkedlist()
llist2.append(nodes['d'])
llist2.append(nodes['e'])
llist2.append(nodes['f'])
llist2.append(nodes['x'])
llist2.append(nodes['y'])
llist2.append(nodes['z'])
#遍历链表1,压入栈1
q1 = []
for v in llist1.all():
q1.append(v)
#遍历链表2,压入栈2
q2 = []
for v in llist2.all():
q2.append(v)
#依次出栈,找到第一个不同的节点
top1 = q1.pop()
top2 = q2.pop()
crossed = None
while top1 == top2:
crossed = top1
top1 = q1.pop()
top2 = q2.pop()
print(crossed)

根据作业描述,链接开始交叉后的元素都是相同的,那么找到交叉点,就转换为从链表尾端开始找到第一个不同的元素。而单向链表是从头访问到尾,所以这里考虑用栈来处理。

首先把两个链表的遍历结果压入栈中,此时两个栈的顶部分别是两个链表的尾部节点,然后两个栈开始出栈并比较出栈节点是否相同。交叉点就是最后一个相同的节点。

输出结果为 x

用户头像

chengjing

关注

程靖 2018.06.06 加入

还未添加个人简介

评论

发布
暂无评论
【week08】作业