现有两个递增有序的整数单链表A和B,设计一个尽可能高效的算法,求两个集合的交集C,C仍然是递增有序的单链表,并给出算法的时间和空间复杂度。例如A=(1, 3, 5, 7),B=(1, 2, 4, 5, 7),交集C=(1, 5, 7)。
时间: 2024-05-05 09:17:11 浏览: 78
算法思路:
由于两个链表都是递增有序的,所以可以使用双指针的方法,分别从链表A和B的头结点开始遍历,比较当前节点的值大小,如果相等则将该节点添加到新的链表C中,同时将两个链表的指针都向后移动一位,如果不相等,则将值小的链表的指针向后移动一位。当其中一个链表遍历完时,就可以停止遍历。
时间复杂度:O(min(m,n)),其中m和n分别是两个链表的长度。
空间复杂度:O(min(m,n)),需要一个新的链表来存储交集C。
Python代码实现:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
pA, pB = headA, headB
dummy = ListNode(0)
tail = dummy
while pA and pB:
if pA.val == pB.val:
tail.next = ListNode(pA.val)
tail = tail.next
pA, pB = pA.next, pB.next
elif pA.val < pB.val:
pA = pA.next
else:
pB = pB.next
return dummy.next
```
阅读全文