写点什么

架构第八周作业

用户头像
Geek_Gu
关注
发布于: 2020 年 11 月 15 日

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用代码(或伪代码)描述算法,并给出时间复杂度。


class Node():
def __init__(self, item): self.item = item self.next = None

class LinkList():
def __init__(self): self.head = None
def is_empty(self): return self.head is None
def length(self): cur = self.head count = 0 while cur is not None: count += 1 cur = cur.next return count
def items(self): cur = self.head while cur is not None: yield cur.item cur = cur.next
def append(self, item): '''尾插''' node = Node(item) if self.is_empty(): self.head = node else: cur = self.head while cur.next is not None: cur = cur.next cur.next = node
def find(self, item): if item in self.items(): return item else: return False

def solution(l1, l2): if l1.head is None or l2.head is None: print('有空链表') return # 判断是否合并 尾部是否相同 for i in l1.items(): pass for j in l2.items(): pass if i != j: print('不合并') return if l1.length() > l2.length(): long, short = l1, l2 else: long, short = l2, l1 g = long.items() cur = long.head for i in range(long.length()-short.length()): item = next(g) cur = cur.next if short.find(item) is not False: print(item) return item node1, node2 = cur, short.head while node1.item != node2.item: node1 = node1.next node2 = node2.next print('合并:', node1.item) return node1.item

def main(): m = LinkList() n = LinkList() data1 = [1, 2, 3, 11, 22] data2 = [4, 5, 6] data3 = [7, 8, 9]
# 空链表 solution(m, n)
# 不合并 for i in data1: m.append(i) for i in data2: n.append(i) solution(m, n)
# 合并 for i in data3: m.append(i) n.append(i) solution(m, n)

if __name__ == '__main__': main()
复制代码

时间复杂度 O(n)


用户头像

Geek_Gu

关注

还未添加个人签名 2019.09.09 加入

还未添加个人简介

评论

发布
暂无评论
架构第八周作业