Python 单链表实现集合并集算法 - 详细解析与代码示例
Python 单链表实现集合并集算法 - 详细解析与代码示例
问题描述:
有两个集合采用整数单链表 A、B 存储,设计一个算法求两个集合的并集 C,C 仍然用单链表存储。并给出算法的时间和空间复杂度。例如 A=(1,3,2),B=(5,1,4,2),并集 C=(1,3,2,5,4)。
实现思路:
- 将 A、B 两个链表中的元素添加到一个新链表 C 中,同时去重。
- 返回链表 C。
时间复杂度: O(n)
空间复杂度: O(n)
Python 代码实现如下:
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
class Solution:
def getUnion(self, head1, head2):
if not head1:
return head2
if not head2:
return head1
# 将链表1的元素添加到链表C中
C = head1
tail = head1
node = head1.next
while node:
if not self.isExist(head1, node.val):
tail.next = node
tail = node
node = node.next
# 将链表2的元素添加到链表C中
node = head2
while node:
if not self.isExist(head1, node.val):
tail.next = node
tail = node
node = node.next
return C
# 判断链表中是否存在某个元素
def isExist(self, head, val):
node = head
while node:
if node.val == val:
return True
node = node.next
return False
# 测试代码
head1 = Node(1, Node(3, Node(2)))
head2 = Node(5, Node(1, Node(4, Node(2))))
s = Solution()
C = s.getUnion(head1, head2)
node = C
while node:
print(node.val)
node = node.next
# 输出:1 3 2 5 4
代码解析:
- Node 类: 定义单链表节点类,包含节点值
val和指向下一个节点的指针next。 - Solution 类:
getUnion(head1, head2)方法:接受两个链表的头节点head1和head2作为参数,返回并集链表的头节点。isExist(head, val)方法:判断链表中是否存在某个元素val。
- 测试代码: 创建两个链表
head1和head2,调用getUnion方法得到并集链表C,然后遍历输出C的所有节点值。
算法流程:
- 初始化一个新链表
C,将链表head1作为C的头节点。 - 遍历链表
head1,并将每个节点值添加到C中,同时判断该节点值是否已经在C中存在,如果存在则不添加。 - 遍历链表
head2,并将每个节点值添加到C中,同样进行去重操作。 - 返回链表
C的头节点。
时间复杂度分析:
- 遍历两个链表各一次,时间复杂度为 O(n)。
- 去重操作需要遍历链表,时间复杂度为 O(n)。
- 因此,整个算法的时间复杂度为 O(n)。
空间复杂度分析:
- 新链表
C的空间复杂度为 O(n),因为C中最多包含 n 个节点。 - 因此,整个算法的空间复杂度为 O(n)。
原文地址: https://www.cveoy.top/t/topic/mS1b 著作权归作者所有。请勿转载和采集!