已知两个非降序链表序列s1与s2,设计函数构造出s1与s2的交集新链表s3
时间: 2023-05-31 12:17:57 浏览: 800
两个有序链表序列的合并_C语言_
5星 · 资源好评率100%
### 回答1:
可以使用双指针法来解决这个问题。定义两个指针p1和p2分别指向s1和s2的头节点,然后比较p1和p2节点的值,如果相等,则将该节点加入新链表s3中,并将p1和p2指针同时向后移动一位;如果p1节点的值小于p2节点的值,则将p1指针向后移动一位;如果p1节点的值大于p2节点的值,则将p2指针向后移动一位。直到p1或p2指针为空为止,此时s3就是s1和s2的交集新链表。
具体实现可以参考以下代码:
```
struct ListNode* getIntersection(struct ListNode* s1, struct ListNode* s2) {
struct ListNode* p1 = s1;
struct ListNode* p2 = s2;
struct ListNode* s3 = NULL;
struct ListNode* tail = NULL;
while (p1 && p2) {
if (p1->val == p2->val) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = p1->val;
node->next = NULL;
if (s3 == NULL) {
s3 = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
p1 = p1->next;
p2 = p2->next;
} else if (p1->val < p2->val) {
p1 = p1->next;
} else {
p2 = p2->next;
}
}
return s3;
}
```
### 回答2:
算法思路:
由于两个链表是非降序的,那么可以考虑使用双指针的方法。分别用指针p1和p2指向两个链表的表头,然后比较p1和p2对应的节点的大小。
1. 如果p1节点的值小于p2节点的值,那么将p1往后移动一位。
2. 如果p1节点的值大于p2节点的值,那么将p2往后移动一位。
3. 如果p1节点的值等于p2节点的值,那么将p1和p2都往后移动一位,并将该节点的值加入到新链表中。
代码实现:
C++代码如下:
```c++
#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* getIntersection(ListNode* headA, ListNode* headB) {
ListNode* p1 = headA;
ListNode* p2 = headB;
ListNode* res = new ListNode(-1); // 新链表
ListNode* p3 = res;
while (p1 != NULL && p2 != NULL) {
if (p1->val < p2->val) {
p1 = p1->next;
} else if (p1->val > p2->val) {
p2 = p2->next;
} else {
p3->next = new ListNode(p1->val);
p1 = p1->next;
p2 = p2->next;
p3 = p3->next;
}
}
p3 = res->next;
delete res; // 释放内存
return p3;
}
int main() {
ListNode* a1 = new ListNode(1);
ListNode* a2 = new ListNode(2);
ListNode* a3 = new ListNode(3);
ListNode* a4 = new ListNode(4);
a1->next = a2;
a2->next = a3;
a3->next = a4;
ListNode* b1 = new ListNode(2);
ListNode* b2 = new ListNode(4);
ListNode* b3 = new ListNode(6);
b1->next = b2;
b2->next = b3;
ListNode* res = getIntersection(a1, b1);
while (res != NULL) {
cout << res->val << " ";
res = res->next;
}
return 0;
}
```
Python代码如下:
```python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1: ListNode
:type head2: ListNode
:rtype: ListNode
"""
p1 = headA
p2 = headB
res = ListNode(-1)
p3 = res
while p1 is not None and p2 is not None:
if p1.val < p2.val:
p1 = p1.next
elif p1.val > p2.val:
p2 = p2.next
else:
p3.next = ListNode(p1.val)
p1 = p1.next
p2 = p2.next
p3 = p3.next
p3 = res.next
del res
return p3
```
时间复杂度:
由于要遍历两个链表,时间复杂度为O(m+n),其中m和n分别是两个链表的长度。
空间复杂度:
因为要构造一个新链表,所以空间复杂度为O(min(m,n)),其中m和n分别是两个链表的长度。
### 回答3:
解题思路:
由于s1与s2都是非降序链表序列,因此可以考虑从头开始比较s1和s2的元素,并将相同的元素加入到新链表s3中。具体来说,可以定义两个指针p1和p2分别指向s1和s2的头结点,不断地比较它们的元素大小,将相同的元素加入到s3中,并将指针p1和p2往后移动,直至其中一个链表遍历完。代码如下所示。
代码实现:
struct ListNode* getIntersectionNode(struct ListNode* s1, struct ListNode* s2) {
struct ListNode dummy; // 定义头结点
struct ListNode* tail = &dummy; // 定义尾指针
struct ListNode *p1 = s1, *p2 = s2;
while (p1 && p2) { // 当两个链表都没有遍历完时
if (p1->val == p2->val) { // 相同元素
tail->next = p1; // 将相同元素加入到新链表s3中
tail = p1; // 更新尾指针
p1 = p1->next;
p2 = p2->next;
} else if (p1->val < p2->val) { // s1元素小,p1向后移动
p1 = p1->next;
} else { // s2元素小,p2向后移动
p2 = p2->next;
}
}
tail->next = NULL; // 最后一个元素指向NULL,表示结束
return dummy.next; // 返回新链表s3的头结点
}
时间复杂度:
每次移动p1或p2后,至少有一个指针会指向下一个不同的元素,因此时间复杂度为O(m+n),其中m和n分别为s1和s2的长度。
空间复杂度:
只需要定义常数个指针变量和一个头结点,因此空间复杂度为O(1)。
阅读全文