LeetCode: Intersection of Two Linked Lists

solution 1:

If start comparison at the beginning of two linked lists, it will cost too much time.

So calculate the lengths of two lists, cut the extra part from the longer list and start comparing  element of the same position in two lists.

This is because if there are intersection, elements in intersection part have same position from the end to beginning of two lists.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA=0; int lenB=0; ListNode *ptA=headA; ListNode *ptB=headB; while(ptA){ lenA++; ptA=ptA->next; } while(ptB){ lenB++; ptB=ptB->next; } ptA=headA; ptB=headB; if(lenA>lenB){ for(int i=0;i<lenA-lenB;i++){ ptA=ptA->next; } } if(lenA<lenB){ for(int i=0;i<lenB-lenA;i++){ ptB=ptB->next; } } int distance=(lenA>lenB)?lenB:lenA; for(int i=0;i<distance;i++){ if(ptA==ptB) return ptA; ptA=ptA->next; ptB=ptB->next; } return NULL; } };

Solution2: use two pointers. update later

Reference:
http://www.cnblogs.com/yuzhangcmu/p/4128794.html
http://yucoding.blogspot.com/2014/12/leetcode-question-intersection-of-two.html
链表常考题目汇总