博文中会简要介绍Leetcode P0160题目分析及解题思路。

“Intersection of Two Linked Lists”是一道非常巧妙的题目， 这道题在O(n)的是时间复杂度内解决，但是如何保证空间复杂度为O(1)则不容易想到。一般来说在不追求空间复杂度更低的情况下，可以使用HashTable记录已经遍历过的结点，若发现当前遍历的结点在HashTable中出现过，那么由于是按顺序遍历，这个结点一定是相交的点。不过还有更优的解法。

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. 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.
• Each value on each linked list is in the range [1, 10^9].
• Your code should preferably run in O(n) time and use only O(1) memory.

更优的解法则是巧妙利用了A和B两个链表之间的长度关系。不失一般性地，我们假定A链表更短，若A链表指针和B链表指针同时从各自的表头出发，那么当A链表的指针走到末尾时，B链表指针恰好离结尾差两个链表长度差的长度。

此时若A链表指针开始从B链表的结点开始重新遍历，当它走过两者长度差后，原先的B链表指针则恰好走到末尾，此时B链表指针开始从A链表的头结点开始遍历，则两者走相同的长度后恰好同时到达相交的结点，这样就可以得到交点。

以下是Java的题解代码实现。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA, l2 = headB;
        while (l1 != l2) {
            l1 = (l1 == null)? headB: l1.next;
            l2 = (l2 == null)? headA: l2.next;
        }
        
        return l1;
    }
}

以下是C++的题解代码实现。

/**
 * 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) {
        unordered_set<ListNode*> node_set;
        
        ListNode *l1 = headA, *l2 = headB;
        while (l1 || l2) {
            if (l1) {
                if (node_set.count(l1) > 0)
                    return l1;
                
                node_set.insert(l1);
                l1 = l1->next;
            }
            
            if (l2) {
                if (node_set.count(l2) > 0)
                    return l2;
                
                node_set.insert(l2);
                l2 = l2->next;
            }
        }
        
        return nullptr;
    }
};