1. 题目描述

problem link

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.

2. 解题

方法1

先算出两个单链表长度的差值，然后让较长的单链表先往后走差值步，可知现在两个子链表长度相同，则现在两个链表一起往后走，一定会在第一个交点处相遇。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }

    // 计算两个链表长度的差值
    struct ListNode* ptrA = headA;
    struct ListNode* ptrB = headB;
    int lenA = 0;
    int lenB = 0;

    while (ptrA) {
        lenA++;
        ptrA = ptrA->next;
    }
    while (ptrB) {
        lenB++;
        ptrB = ptrB->next;
    }
    ptrA = headA;
    ptrB = headB;

    // 让较长的链表先向后移动差值步
    for (int i = 0; i < abs(lenA - lenB); i++) {
        if ((lenA - lenB) < 0) {
            ptrB = ptrB->next;
        }
        else {
            ptrA = ptrA->next;
        }
    }

    while (1) {
        if (ptrA == ptrB) {
            return ptrA;
        }
        else if (ptrA == NULL || ptrB == NULL) {
            return NULL;
        }
        else {
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
    }
}

方法2

同样是在长度上做文章，但这次不需要算出两个单链表的长度。首先考虑图中的情况，链表A由x + z组成，链表B由y + z组成。现用两个指针分别指向headA和headB，然后一起往后走，假如A指针走到NULL则把它移动到headB，假如B指针走到NULL则把它移动到headA，然后继续往后走，则可之最终两个指针一定会相遇在交点，因为此时A指针走了x + z + y步，而B指针走了y + z + x步，即相遇在交点。

而且假如两个链表没有交点，则两个指针会在分别走完两个链表长度之和后同时等于NULL，完美判断这种情况。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *p1 = headA;
    struct ListNode *p2 = headB;

    while (p1 != p2) {
        p1 = (p1 == NULL) ? headB : p1->next;
        p2 = (p2 == NULL) ? headA : p2->next;
    }

    return p1;
}