【week08】作业
发布于: 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,zllist1 = 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,zllist2 = 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,压入栈1q1 = []for v in llist1.all(): q1.append(v)#遍历链表2,压入栈2q2 = []for v in llist2.all(): q2.append(v)#依次出栈,找到第一个不同的节点top1 = q1.pop()top2 = q2.pop()crossed = Nonewhile top1 == top2: crossed = top1 top1 = q1.pop() top2 = q2.pop()print(crossed)
根据作业描述,链接开始交叉后的元素都是相同的,那么找到交叉点,就转换为从链表尾端开始找到第一个不同的元素。而单向链表是从头访问到尾,所以这里考虑用栈来处理。
首先把两个链表的遍历结果压入栈中,此时两个栈的顶部分别是两个链表的尾部节点,然后两个栈开始出栈并比较出栈节点是否相同。交叉点就是最后一个相同的节点。
输出结果为 x
划线
评论
复制
发布于: 2020 年 07 月 27 日 阅读数: 35
chengjing
关注
程靖 2018.06.06 加入
还未添加个人简介
评论