[LeetCode] 160. Intersection of Two Linked Lists 解题思路

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:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

问题：判断两个列表是否有相交的元素，若有，找出相交节点。

这题也是一道基础题，看了自己的列表知识还需要巩固下才好。

分别求出两个列表的长度 len1, len2 ，以及他们的长度差异 diff

跳过长度差异部分，对于剩余的相同长度部分，依次检查两个链表的对应节点，若又存在相交节点，则必有两个对应节点相等。

     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

         int len1 = ;

         ListNode* p1 = headA;

         while(p1 != NULL){

             p1 = p1->next;

             len1++;

         }

         int len2 = ;

         ListNode* p2 = headB;

         while(p2 != NULL){

             p2 = p2->next;

             len2++;

         }

         p1 = headA;

         p2 = headB;

         if (len1 > len2){

             int diff = len1 - len2;

             while(diff > ){

                 p1 = p1->next;

                 diff--;

             }

         }

         if (len2 > len1){

             int diff = len2 - len1;

             while(diff > ){

                 p2 = p2->next;

                 diff--;

             }

         }

         while(p1 != NULL ){

             if ( p1 == p2){

                 return p1;

             }

             p1 = p1->next;

             p2 = p2->next;

         }

         return NULL;

     }

参考资料：

LeetCode: Intersection of Two Linked Lists 解题报告, Yu's garden