因为单链表只有一个next指针,所以链表相交只有一种情况,即:
通过观察我们可以发现:
较长的链表的和较短的链表的,从后到前,长度为短链表的长度的部分是一一对应的
通过逆向思维,可以发现,长链表long_len减去短链表short_len为mylen,我们让长链表先走到第mylen个节点,此时在和较短链表进行比较,此时他们是一一对应的。
通过逆向思维,可以发现,长链表long_len减去短链表short_len为mylen,我们让长链表先走到第mylen个节点,此时在和较短链表进行比较,此时他们是一一对应的。
图形解释:
编程思路:
1 先求出两个链表长度 l1 l2
2 如果 l2 比 l1 大,交换它们、以及移动指针,确保 l1 更长
3 长链表 l1 先走 l1 - l2 步
4 再一起走,直到末尾
C++代码:
class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode* move1 = pHead1, *move2 = pHead2; int l1 = Length(pHead1); int l2 = Length(pHead2); //硬性要求1更长 if(l2 > l1){ swap(l1, l2); swap(move1, move2); } //长链表先走 long_len - short_len for(int i = 0; i < l1 - l2; i++) move1 = move1->next; //再一起走 while(move1 && move2){ if(move1 == move2) return move1; move1 = move1->next; move2 = move2->next; } return NULL; } //求链表长度 int Length(ListNode* head){ int length = 0; while(head){ length++; head = head->next; } return length; } };