Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
null
./** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: int getListLength(ListNode* head){ int len = 0; while(head){ len++; head=head->next; } return len; } ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA = getListLength(headA); int lenB = getListLength(headB); ListNode* common = NULL,*startA=headA,*startB=headB; if(lenA<lenB){ int diff = lenB-lenA; while(diff--) startB=startB->next; }else{ int diff = lenA-lenB; while(diff--) startA=startA->next; } while(startA){ if(startA == startB){ common = startA; break; } startA=startA->next; startB=startB->next; } return common; } };
[Linked List]Intersection of Two Linked Lists
原文:http://www.cnblogs.com/zengzy/p/5041278.html