Python 单链表实现集合并集算法 - 详细解析与代码示例

问题描述:

有两个集合采用整数单链表 A、B 存储,设计一个算法求两个集合的并集 C,C 仍然用单链表存储。并给出算法的时间和空间复杂度。例如 A=(1,3,2),B=(5,1,4,2),并集 C=(1,3,2,5,4)。

实现思路:

  1. 将 A、B 两个链表中的元素添加到一个新链表 C 中,同时去重。
  2. 返回链表 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

代码解析:

  1. Node 类: 定义单链表节点类,包含节点值 val 和指向下一个节点的指针 next。
  2. Solution 类:
    • getUnion(head1, head2) 方法:接受两个链表的头节点 head1 和 head2 作为参数,返回并集链表的头节点。
    • isExist(head, val) 方法:判断链表中是否存在某个元素 val。
  3. 测试代码: 创建两个链表 head1 和 head2,调用 getUnion 方法得到并集链表 C,然后遍历输出 C 的所有节点值。

算法流程:

  1. 初始化一个新链表 C,将链表 head1 作为 C 的头节点。
  2. 遍历链表 head1,并将每个节点值添加到 C 中,同时判断该节点值是否已经在 C 中存在,如果存在则不添加。
  3. 遍历链表 head2,并将每个节点值添加到 C 中,同样进行去重操作。
  4. 返回链表 C 的头节点。

时间复杂度分析:

  • 遍历两个链表各一次,时间复杂度为 O(n)。
  • 去重操作需要遍历链表,时间复杂度为 O(n)。
  • 因此,整个算法的时间复杂度为 O(n)。

空间复杂度分析:

  • 新链表 C 的空间复杂度为 O(n),因为 C 中最多包含 n 个节点。
  • 因此,整个算法的空间复杂度为 O(n)。
Python 单链表实现集合并集算法 - 详细解析与代码示例

原文地址: https://www.cveoy.top/t/topic/mS1b 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录