已知两个链表A[1,2,4,5,6]和B[2,4,6,8]分别表示两个集合,其 元素递增排列。请设计一个算法,用于求出 A与B的交集,并存放 在C链表中。python
时间: 2024-10-13 09:09:05 浏览: 15
为了找出链表A和B的交集并存储在新的链表C中,可以采用双指针法。以下是Python的一个解决方案:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
# 定义两个指针,一个遍历链表A,另一个遍历链表B
pointerA = headA
pointerB = headB
# 计算两个链表的长度差
len_diff = abs(len(headA) - len(headB))
if len_diff > 0:
# 如果A比B长,移动较长链表的指针直到长度相等
for _ in range(len_diff):
if pointerA is not None:
pointerA = pointerA.next
else:
return None # 如果A为空,说明没有交集
elif len_diff == 0: # 如果长度相等,直接开始比较
pass
else:
raise ValueError("Invalid input: both lists have zero length")
while pointerA != pointerB:
# 指针同时向后移动
pointerA = pointerA.next if pointerA is not None else headB
pointerB = pointerB.next
# 当找到相同的节点时,返回该节点作为交集
return pointerA
# 示例链表
A = ListNode(1, ListNode(2, ListNode(4, ListNode(5, ListNode(6))))
B = ListNode(2, ListNode(4, ListNode(6, ListNode(8))))
# 创建交集链表
intersection = getIntersectionNode(A, B)
if intersection:
print("交集链表:", [node.val for node in iterateListNode(intersection)])
else:
print("没有交集")
def iterateListNode(node):
current = node
while current:
yield current.val
current = current.next
```
这个函数首先计算两个链表的有效长度差,然后通过移动指针使它们同步到相同位置。最后,如果两个指针指向的是同一个节点,则找到了交集。如果在任何时候有一个链表的所有元素都遍历完了还没有找到交点,那么说明没有交集。
阅读全文