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.

(1)自己最原始的方法是建立一个set存储公共节点，再遍历其中的任何一个链表，最先在set中出现的节点就是所求的节点 (2)遍历找到各链表的尾节点，并求出各链表的长度，让长的链表先走多出的链表长度，那么他们一定会在交汇点相遇。

/**
 * 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) {
        if (!headA || !headB)  return NULL;
        //判断是否相交，尾节点是否相等
        ListNode *preA = headA, *preB = headB;
        int lenA = 1, lenB = 1;
        //求出A的尾节点和长度
        while(preA->next){
            lenA++;
            preA = preA->next;
        }
        while(preB->next){
            lenB++;
            preB = preB->next;
        }
        if (preA != preB) return NULL;

        //长的链表先走多余出的长度|lenA - lenB|
        preA = headA;
        preB = headB;
        if(lenA > lenB){
            for(int i = 0; i < lenA -lenB; i++){
                preA = preA->next;
            }
        }else{
            for(int i = 0; i < lenB -lenA; i++){
                preB = preB->next;
            }
        }
        while(preA && preB){
                if(preA != preB){
                    preA = preA->next;
                    preB = preB->next;
                }else{
                    return preA;
                }
        }
    }
};

(3)巧妙的方法，当其中的一个遍历完时，将它置为另一个链表的头，直到他们相等，如果他们没有公共节点，则相遇的节点一定是NULL节点；如果有公共节点，一定相遇在公共节点。

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

上述的遍历过程为
A: a1->a2->c1->c2->c3->b1->b2->b3->c1

                                   |

B: b1->b2->b3->c1->c2->c3->a1->a2->c1

/**
 * 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) {
        if(headA == NULL || headB == NULL)  return NULL;

        ListNode *p1 = headA, *p2 = headB;

        /*while(p1 != p2){
            p1 = p1->next;
            p2 = p2->next;

            //这三个if语句的顺序不能调换，在没有公共节点时，这条语句返回NULL,这句很重要，如果没有这句，在没有公共节点的情况会进入死循环
            if(p1 == p2)    return p1;

            if(p1 == NULL)
                p1 = headB;
            if(p2 == NULL)
                p2 = headA;
        }
        //or return p1;
        return p2;
    }*/
    while(p1 != p2){
      p1 = p1?p1->next:headB;
      p2 = p2?p2->next:headA;
    }
    return p1;
};