用C语言给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
时间: 2023-04-12 13:00:31 浏览: 68
这是一个编程类的问题,我可以回答。这个问题可以使用双指针法来解决。首先分别遍历两个链表,得到它们的长度。然后让较长的链表先走 abs(lenA - lenB) 步,使得两个链表剩余的长度相等。接着,同时遍历两个链表,比较它们的节点是否相同,如果相同则说明找到了相交节点,返回该节点即可。如果遍历完两个链表都没有找到相交节点,则返回 null。
以下是示例代码:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int lenA = 0, lenB = 0;
struct 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 = 0; i < lenA - lenB; i++) {
pA = pA->next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
pB = pB->next;
}
}
while (pA && pB) {
if (pA == pB) {
return pA;
}
pA = pA->next;
pB = pB->next;
}
return NULL;
}