判断两个链表是否相交
时间: 2023-08-13 12:08:08 浏览: 67
要判断两个链表是否相交,可以使用以下的方法:
1. 遍历第一个链表,将每个节点的地址存储在一个集合中。
2. 遍历第二个链表,检查每个节点的地址是否在集合中存在。如果存在,则两个链表相交;如果不存在,则两个链表不相交。
这种方法的时间复杂度是O(m+n),其中m和n分别是两个链表的长度。需要额外的空间来存储节点地址的集合。
另外,如果两个链表相交,它们在相交点之后的节点都是相同的。因此,可以先遍历两个链表,得到它们的长度差diff。然后让较长的链表先走diff步,然后同时遍历两个链表,直到找到相同的节点或者遍历结束。这种方法的时间复杂度为O(max(m,n)),不需要额外的空间。
相关问题
c++判断两个单链表是否相交
以下是C++判断两个单链表是否相交的代码实现:
```c++
//定义链表节点
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//判断两个单链表是否相交(判断尾节点是否相同)
bool isIntersect(ListNode* p1, ListNode* p2) {
ListNode* pHead1 = p1;
ListNode* pHead2 = p2;
if (pHead1 == nullptr || pHead2 == nullptr) {
return false;
}
while (pHead1->next != nullptr) {
pHead1 = pHead1->next;
}
while (pHead2->next != nullptr) {
pHead2 = pHead2->next;
}
//判断尾节点是否相同
if (pHead1 == pHead2) {
return true;
} else {
return false;
}
}
```
判断两个链表相交的交点
可以使用双指针法求解。首先遍历两个链表,得到它们的长度。然后让长的链表先走多出的长度,让两个链表剩下的长度相等。最后同时遍历两个链表,找到相同的节点即为它们的交点。如果没有相交的节点,就返回 null。
下面是 Java 代码实现:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int lenA = getLength(headA);
int lenB = getLength(headB);
ListNode curA = headA;
ListNode curB = headB;
if (lenA > lenB) {
int diff = lenA - lenB;
while (diff > 0) {
curA = curA.next;
diff--;
}
} else if (lenB > lenA) {
int diff = lenB - lenA;
while (diff > 0) {
curB = curB.next;
diff--;
}
}
while (curA != null && curB != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
private int getLength(ListNode node) {
int count = 0;
while (node != null) {
count++;
node = node.next;
}
return count;
}
}