给定两个单链表,编写算法找出两个链表的公共结点。
时间: 2023-04-26 14:06:27 浏览: 112
两个链表的第一个公共结点.md
可以使用双指针法来解决这个问题。首先,分别遍历两个链表,得到它们的长度。然后,让较长的链表的指针先走若干步,使得两个链表剩余的长度相等。接着,同时遍历两个链表,直到找到第一个相同的结点,即为它们的公共结点。如果没有公共结点,则返回空指针。
具体实现可以参考以下代码:
```
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;
}
```
阅读全文