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:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

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.

---

给定两个链表，如果这两个链表在某个点相交，并且此后合并为一个链表，要找出这个交点；如果不想交，返回NULL。 简单的方法是，如果两个链表相交，比如题图在c1相交，则对于两个链表，从相交点往后长度是一样的，所以我们可以先求出两个链表的长度，假设长度差是delta，则较长链表先前进delta步，此时长短链表的往后的路都是一样长了，这样两个链表一起走，如果发现有相等的节点，则是相交节点，否则两个链表不相交。 本思路代码如下：

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
    {
        int len1 = 0, len2 = 0;
        ListNode *h1 = headA, *h2 = headB;
        while (h1) {
            ++len1;
            h1 = h1->next;
        }
        while (h2) {
            ++len2;
            h2 = h2->next;
        }
        h1 = headA;
        h2 = headB;
        if (len1 > len2) {
            while (len1 > len2) {
                h1 = h1->next;
                –len1;
            }
        }
        else if (len2 > len1) {
            while (len2 > len1) {
                h2 = h2->next;
                –len2;
            }
        }
        while (h1 && h2 && h1 != h2) {
            h1 = h1->next;
            h2 = h2->next;
        }
        if (!h1 || !h2)
            return NULL;
        else
            return h1;
    }
};

本代码提交AC，用时39MS。
还有一种思路很巧妙，参考：http://www.cnblogs.com/yuzhangcmu/p/4128794.html
具体是这样的，比如题目中的例子，假设指针pA和pB分别指向A,B两个链表，两个指针同时不断的一步一步走，当pA走到结尾时，pA指向B链表表头开始走，同理当pB走到结尾时，pB指向A链表表头开始走。不断的走，当pA和pB指向同一个节点时，就是那个相交的节点。这个很巧妙呀，当pA和pB走到相交点时，他们走过的路程其实是相等的，比如题目中，他们都走了9个节点后相遇了。
代码如下：

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
    {
        if (headA == NULL || headB == NULL)
            return NULL;
        ListNode *h1 = headA, *h2 = headB;
        ListNode *tail1 = NULL, *tail2 = NULL;
        while (true) {
            if (h1 == NULL)
                h1 = headB;
            if (h2 == NULL)
                h2 = headA;
            if (h1->next == NULL)
                tail1 = h1;
            if (h2->next == NULL)
                tail2 = h2;
            if (tail1 != NULL && tail2 != NULL && tail1 != tail2)
                return NULL;
            if (h1 == h2)
                return h1;
            h1 = h1->next;
            h2 = h2->next;
        }
    }
};

本代码提交AC，用时36MS。

三刷。同样的思路：

class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		if (headA == NULL || headB == NULL)return NULL;
		ListNode *la = headA, *lb = headB;
		bool la_changed = false, lb_changed = false;
		while (la != lb) {
			la = la->next;
			lb = lb->next;
			if (la == NULL) {
				if (la_changed)return NULL;
				else {
					la = headB;
					la_changed = true;
				}
			}
			if (lb == NULL) {
				if (lb_changed)return NULL;
				else {
					lb = headA;
					lb_changed = true;
				}
			}
		}
		return la;
	}
};

本代码提交AC，用时68MS。