题目:
描述
给你两个单链表的头节点headA和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
接口
struct ListNode *getIntersectionNode
(struct ListNode *headA, struct ListNode *headB) { }
示例
思路
走差距步,比地址不比值
可以想象的到,如果长的和短的一起走,走到相等的值不就是相同节点吗?
但是也可能会出现这种情况:
那么这样的话,比值就不可行了,但是如果节点相交,他们的地址一定是相同的 。
也由此,我们可以通过最后的一个节点判断他们是否相交,如果他们最后一个节点地址相同,则相交,我们去找相交节点,否则返回NULL。
实现代码
int lenA = 1; int lenB = 1; struct ListNode* curA = headA; while(curA->next) { lenA++; curA = curA->next; } struct ListNode* curB = headB; while(curB->next) { lenB++; curB = curB->next; } if(curA != curB) return NULL; struct ListNode* fast = headA; struct ListNode* slow = headB; if(lenA < lenB) { fast = headB; slow = headA; } int k = abs(lenA-lenB); while(k--) { fast = fast->next; } while(fast != slow) { if(fast == slow) return fast; fast = fast->next; slow = slow->next; } return fast;