已知两个非降序链表序列s1与s2,设计函数构造出s1与s2的交集新链表s3。
时间: 2023-05-31 11:19:32 浏览: 213
两个链表求交集(链表基础练习)
### 回答1:
可以使用双指针算法来构造s1与s2的交集新链表s3。首先定义两个指针分别指向s1和s2的头结点,比较它们的值,如果相等,则将该值加入s3中,并将两个指针同时向后移动;如果s1的值小于s2的值,则将s1指针向后移动;如果s1的值大于s2的值,则将s2指针向后移动。重复上述操作直到两个指针中有一个到达链表尾部。
### 回答2:
题目要求我们设计一个函数,输入为两个非降序链表s1和s2,输出为它们的交集新链表s3。先来分析一下如何遍历两个链表找出共同的元素。
我们可以用两个指针p1和p2分别指向s1和s2的头结点,然后用循环遍历两个链表,比较p1和p2当前指向的元素大小。如果p1指向的元素小于p2指向的元素,则p1向后移动一个指针,否则p2向后移动一个指针。如果p1和p2指向的元素相等,则将该元素加入新链表s3,同时p1和p2都向后移动一个指针。
找出两个链表的交集后,我们可以用类似插入排序的方法,用一个指针p3遍历新链表s3上的元素,同时用另一个指针p4指向已排序的元素,比较大小后插入到正确的位置。最后返回新链表s3即可。
以下是伪代码实现:
```
Node* intersection(Node* s1, Node* s2) {
Node* s3 = NULL; // 新链表头结点
Node* p1 = s1; // 指向s1的指针
Node* p2 = s2; // 指向s2的指针
// 循环遍历两个链表,比较大小
while (p1 != NULL && p2 != NULL) {
if (p1->data < p2->data) {
p1 = p1->next;
} else if (p1->data > p2->data) {
p2 = p2->next;
} else {
// 记录相等的元素到新链表s3
Node* node = new Node(p1->data);
node->next = s3;
s3 = node;
p1 = p1->next;
p2 = p2->next;
}
}
// 将新链表s3按从小到大排序
Node* p3 = s3; // 指向未排序的节点
Node* p4; // 指向已排序的节点
while (p3 != NULL) {
Node* tmp = p3->next;
if (s3 == NULL || s3->data >= p3->data) {
p3->next = s3;
s3 = p3;
} else {
p4 = s3;
while (p4->next != NULL && p4->next->data < p3->data) {
p4 = p4->next;
}
p3->next = p4->next;
p4->next = p3;
}
p3 = tmp;
}
return s3;
}
```
注意,在代码中要保证没有内存泄漏的问题,需要在不需要节点时释放其空间。另外,数据类型和变量名可以根据实际情况进行修改。
### 回答3:
首先需要了解什么是链表以及链表的非降序性质。链表是一种数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。非降序指的是链表中的每个节点的值都大于等于前一个节点的值。
在此基础上,我们可以依次遍历s1和s2链表,并将值相同的节点添加到新的链表s3中。可以使用两个指针分别指向s1和s2的头结点,比较它们的值大小,若相等则将该节点添加到s3中,并将两个指针同时向后移动;如果不相等则移动值较小的指针直到找到与另一个指针值相等的节点或者指针到达链表尾部。直至其中一个链表遍历完毕,新链表s3即为s1和s2的交集。
具体实现可以使用循环结构来完成,其中需要注意边界条件以及链表遍历时要谨慎判断空指针。以下是一份代码实现(C++):
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* getIntersection(ListNode* s1, ListNode* s2) {
ListNode* s3 = NULL; // 初始化新链表
ListNode* p1 = s1; // 声明链表指针1
ListNode* p2 = s2; // 声明链表指针2
while (p1 && p2) { // 当两个链表都不为空时
if (p1->val == p2->val) { // 如果值相等
if (!s3 || s3->val != p1->val) { // 如果该节点不属于交集或者交集中已经有该节点了
ListNode* node = new ListNode(p1->val); // 创建新节点
node->next = s3; // 将节点插入到交集链表开头
s3 = node;
}
p1 = p1->next; // 指针同时后移
p2 = p2->next;
} else if (p1->val < p2->val) { // 如果值不等,移动数值小的指针
p1 = p1->next;
} else {
p2 = p2->next;
}
}
return s3; // 返回交集链表
}
以上代码只是一种实现方式,可能并不是最优解。在实际应用中,需要根据具体的问题场景和数据特点进行优化。
阅读全文