题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 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 *pointA = headA;
        ListNode *pointB = headB;

        //指针 pointA 和 指针 pointB 不断向后遍历，直到找到相交点
        // 不用担心会跳不出这个循环，实际上在链表 headA 长度和链表 headB 长度的之和减一
        // pointA 和 pointB 都会同时指向 null
        while(pointA != pointB)
        {
            pointA  = pointA == NULL? headB : pointA->next;
            pointB = pointB == NULL ? headA : pointB->next;
        }

        return pointA;
    }
};