已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。
时间: 2024-03-16 15:21:22 浏览: 151
项目2_1751022_李翠琪1
算法如下:
1. 设置两个指针p1和p2分别指向S1和S2的头节点。
2. 创建一个新链表S3,设置一个指针p3指向S3的头节点。
3. 循环遍历S1和S2,比较p1指向的节点和p2指向的节点的值,如果相等,则将该节点加入S3中,同时p1和p2都向后移动一位;如果不相等,则将值较小的指针向后移动一位。
4. 循环结束后,返回S3。
Python代码如下:
```
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def intersection(S1: ListNode, S2: ListNode) -> ListNode:
p1, p2 = S1, S2
dummy = ListNode(0)
p3 = dummy
while p1 and p2:
if p1.val == p2.val:
p3.next = ListNode(p1.val)
p3 = p3.next
p1 = p1.next
p2 = p2.next
elif p1.val < p2.val:
p1 = p1.next
else:
p2 = p2.next
return dummy.next
```
阅读全文