求两个单链表表示的集合的交集,并用一个新的带头结点单链表保存并返回表头地址
时间: 2024-10-09 21:14:31 浏览: 12
求两个单链表表示的集合的交集,可以采用“两次遍历”的策略。首先,我们需要定义两个指针,分别指向两个链表的头部。然后,我们可以创建一个空链表作为结果存储交集元素。
1. 初始化两个指针 `p1` 和 `p2` 分别指向第一个链表的头部和第二个链表的头部。
2. 然后开始循环,直到其中一个指针到达链表尾部:
- 如果两个指针所指的节点值相等,说明找到了交集元素,将当前节点添加到结果链表中(如果还没有),并将两个指针都移动到下一个节点。
- 否则,如果第一个链表的节点值小于第二个链表的节点值,移动 `p1` 到下一个节点;如果相反,移动 `p2` 到下一个节点。
3. 遍历结束后,结果链表的最后一个节点就是两个链表交集的结束位置(如果没有交集,结果链表为空)。
以下是算法流程的伪代码:
```python
def findIntersection(list1_head, list2_head):
result_head = None
p1, p2 = list1_head, list2_head
while p1 and p2:
if p1.val == p2.val:
# 创建新的节点并连接到结果链表
new_node = ListNode(p1.val)
if not result_head:
result_head = new_node
else:
current = result_head
while current.next:
current = current.next
current.next = new_node
p1 = p1.next
p2 = p2.next
elif p1.val < p2.val:
p1 = p1.next
else:
p2 = p2.next
return result_head
```