给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构
分别定义两个指针,p和q,把链表a和b的头指针赋值给p、q。然后让p、q挨个往下一个结点移动,如果移动到null就从切换到另外的链表头结点继续移动。直到p和q相等,也就是移动到相同的位置,此时的p或q就是相交的结点位置。然后返回p或q,就算俩链表不相交,也没事,最终返回的大不了是null。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode*p=headA;
ListNode*q=headB;
while(p!=q)
{
if(p!=NULL)
{
p=p->next;
}
else
{
p=headB;
}
if(q!=NULL)
{
q=q->next;
}
else
{
q=headA;
}
}
return p;
}
};