现有两个递增有序的整数单链表A和B,设计一个尽可能高效的算法,求两个集合的交集C,C仍然是递增有序的单链表,并给出算法的时间和空间复杂度。例如A=(1, 3, 5, 7),B=(1, 2, 4, 5, 7),交集C=(1, 5, 7)。python写法有几种,罗列出来
时间: 2024-05-10 08:20:20 浏览: 18
1. 双指针法,时间复杂度O(m+n),空间复杂度O(1)
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def intersection(A: ListNode, B: ListNode) -> ListNode:
dummy = ListNode(0)
cur = dummy
while A and B:
if A.val == B.val:
cur.next = ListNode(A.val)
cur = cur.next
A = A.next
B = B.next
elif A.val < B.val:
A = A.next
else:
B = B.next
return dummy.next
```
2. 哈希表法,时间复杂度O(m+n),空间复杂度O(min(m,n))
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def intersection(A: ListNode, B: ListNode) -> ListNode:
hashset = set()
while A:
hashset.add(A.val)
A = A.next
dummy = ListNode(0)
cur = dummy
while B:
if B.val in hashset:
cur.next = ListNode(B.val)
cur = cur.next
B = B.next
return dummy.next
```
3. 递归法,时间复杂度O(m+n),空间复杂度O(max(m,n))
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def intersection(A: ListNode, B: ListNode) -> ListNode:
if not A or not B:
return None
if A.val == B.val:
node = ListNode(A.val)
node.next = intersection(A.next, B.next)
return node
elif A.val < B.val:
return intersection(A.next, B)
else:
return intersection(A, B.next)
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)