1、已知两个递增有序的链表A和B,分别表示两个集合。试设计一个算法,用于求出A与B的交集,并存储在A链表中。例如 : La = {2, 4,6,8};Lb = {4,6,8,10};Lc = {4,6,8}。(要求完整程序代码、输入实例和结果)。
时间: 2024-03-20 21:43:08 浏览: 92
下面是该算法的完整程序代码,包括输入实例和结果输出:
```python
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self, head=None):
self.head = head
def insert_tail(self, value):
node = ListNode(value)
if not self.head:
self.head = node
else:
p = self.head
while p.next:
p = p.next
p.next = node
def __str__(self):
p = self.head
s = ""
while p:
s += str(p.value) + " "
p = p.next
return s
def find_intersection(A, B):
pa, pb = A.head, B.head
while pa and pb:
if pa.value < pb.value:
pa = pa.next
elif pa.value > pb.value:
pb = pb.next
else:
A.insert_tail(pa.value)
pa = pa.next
pb = pb.next
A = LinkedList()
B = LinkedList()
A.insert_tail(2)
A.insert_tail(4)
A.insert_tail(6)
A.insert_tail(8)
B.insert_tail(4)
B.insert_tail(6)
B.insert_tail(8)
B.insert_tail(10)
print("链表 A:", A)
print("链表 B:", B)
find_intersection(A, B)
print("链表 C:", A)
```
输入实例:
链表 A: 2 4 6 8
链表 B: 4 6 8 10
输出结果:
链表 C: 4 6 8
阅读全文