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.
  找到相交的结点，很简单的题目，用双指针记录两个链表，如果相等则返回结点，如果没有则一直next下去，尽头没有next了就返回空。当其中一个指针走完的时候，就重定向到另外一个链表，这样子就可以让两个指针步数一致。在第二次迭代同时碰到交叉点结点。最后的时间复杂度是两个链表的长度之和，考虑最坏情况O(m+n)。例:A={1,2,3,4,5},B={6,7,8,3,4,5}。A的长度比B小，A先走完了，此时B走到4的位置，A重定向后在链表B的6的位置，此时B走到5，然后B重定向到A链表的位置1，最后两个指针距离交叉点3的步数一致。
  1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     struct ListNode *next; 6  * }; 7  */ 8 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { 9     if(!headA || !headB)    return NULL;10     struct ListNode *pa=headA,*pb=headB;11     while(1){12         if(pa==pb)  13             return pa;14         else if(!pa->next && !pb->next) 15             return NULL;16         else{17             if(pa->next)    18                 pa=pa->next;19             else    20                 pa=headB;21             if(pb->next)22                 pb=pb->next;23             else24                 pb=headA;25         }26     } 27 }

   

  看到别的大神更简洁的写法,同样的原理:
  1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     struct ListNode *next; 6  * }; 7  */ 8 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { 9     if(!headA || !headB)    return NULL;10     struct ListNode *pa=headA,*pb=headB;11     while(pa!=pb){12         pa=pa==NULL?headB:pa->next;13         pb=pb==NULL?headA:pb->next;14     }15     return pa;16 }