数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中两个链表的交集
链表是一种线性数据结构，其中每个节点有两个块，一个块包含节点的值或数据，另一个块包含下一个字段的地址。
假设我们有一个链表，每个节点都包含一个随机指针，该指针指向列表中的其他节点。任务是找到两个链表相互交叉的节点。如果它们没有交集，则返回 NULL 或空作为输出。
例如
输入-1
输出
2
说明：由于给定的链表在值为“2”的节点处相交，因此我们将返回“2”作为输出。
输入-2
输出
NULL
说明：由于没有公共点，因此在这种情况下我们将返回 NULL。
解决此问题的方法
我们有两个链表，它们在某个公共点相互交叉。为了找到交点，我们将遍历这两个链表，直到我们发现它们都指向相同的值。在某些时候，链表的下一个节点的指针将相同。因此，我们将返回该点的值。
- 取两个链表，分别包含数据和指向下一个节点的指针。
- 一个函数 commonPoint(listnode*headA, listnode*headB) 分别接收两个链表的指针，并返回链表的公共点或交点的值。
- 一个查找链表长度的整数函数将返回从列表头部开始的两个链表的长度。
- 现在创建一个指向两个列表头的指针，并遍历长度较长的列表，直到 (第一个列表的长度 - 第二个列表的长度)。
- 现在遍历列表，直到我们找到下一个指针相等。
- 返回这两个列表相交的特定节点的值。
示例
#include <bits/stdc++.h>
using namespace std;
class listnode {
public:
int data;
listnode * next;
};
// Find the length of the linked list
int count(listnode * head) {
int count = 0;
while (head != NULL) {
count++;
head = head -> next;
}
return count;
}
//Function to get the common point of two linked list
int commonPoint(listnode * headA, listnode * headB) {
int len1 = count(headA);
int len2 = count(headB);
listnode * p1 = headA;
listnode * p2 = headB;
if (len1 > len2) {
for (int i = 0; i < len1 - len2; ++i) {
p1 = p1 -> next;
}
}
if (len1 < len2) {
for (int i = 0; i < len2 - len1; ++i) {
p2 = p2 -> next;
}
}
while (p1 != NULL and p2 != NULL) {
if (p1 == p2) {
return p1 -> data;
}
p1 = p1 -> next;
p2 = p2 -> next;
}
return -1;
}
int main() {
listnode * head;
listnode * headA = new listnode();
headA -> data = 5;
listnode * headB = new listnode();
headB -> data = 4;
head = new listnode();
head -> data = 9;
headB -> next = head;
head = new listnode();
head -> data = 2;
headB -> next -> next = head;
head = new listnode();
head -> data = 7;
headA -> next = head;
headB -> next -> next -> next = head;
head = new listnode();
head -> data = 3;
headA -> next -> next = head;
headA -> next -> next -> next = NULL;
cout << commonPoint(headA, headB) << endl;
}运行以上代码将生成以下输出：
输出
7
说明：给定的链表在“7”处合并。
更新于：2021年2月23日
1K+ 次查看
广告