给定两个单链表,编写算法找出两个链表的公共结点,并以代码实现
时间: 2024-05-30 11:14:41 浏览: 15
以下是实现代码:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
ListNode* pA = headA, *pB = headB;
while (pA != pB) {
pA = pA ? pA->next : headB;
pB = pB ? pB->next : headA;
}
return pA;
}
笑话:为什么程序员喜欢包容错误呢?因为try catch比较好写~
相关问题
给定两个单链表,编写算法找出两个链表的公共结点
好的,以下是用中文回答您的问题:
假设我们有两个单链表,它们的节点数不一定相等,现在需要找出它们的公共结点。
为了找出两个单链表的公共结点,我们可以使用以下算法:
1. 先遍历第一个链表,记录下链表的长度为len1。
2. 再遍历第二个链表,记录下链表的长度为len2。
3. 如果len1 > len2,则让第一个链表的指针p1先走len1-len2步。
如果len2 > len1,则让第二个链表的指针p2先走len2-len1步。
4. 然后同时遍历第一个链表和第二个链表,比较它们的每个结点是否相同。
如果相同,就找到了它们的公共结点。
如果不相同,就继续遍历下一个结点,直到找到公共结点或者到达链表的末尾。
这个算法的时间复杂度是O(len1+len2),其中len1和len2分别是两个链表的长度。
给定两个单链表,编写算法找出两个链表的公共结点。
可以使用双指针法来解决这个问题。首先,分别遍历两个链表,得到它们的长度。然后,让较长的链表的指针先走若干步,使得两个链表剩余的长度相等。接着,同时遍历两个链表,直到找到第一个相同的结点,即为它们的公共结点。如果没有公共结点,则返回空指针。
具体实现可以参考以下代码:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = , lenB = ;
ListNode *pA = headA, *pB = headB;
while (pA) {
lenA++;
pA = pA->next;
}
while (pB) {
lenB++;
pB = pB->next;
}
pA = headA;
pB = headB;
if (lenA > lenB) {
for (int i = ; i < lenA - lenB; i++) {
pA = pA->next;
}
} else {
for (int i = ; i < lenB - lenA; i++) {
pB = pB->next;
}
}
while (pA && pB) {
if (pA == pB) {
return pA;
}
pA = pA->next;
pB = pB->next;
}
return NULL;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)