链表相交

描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

示例 2：

示例 3：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

第一种思路是分别定义两指针指向各自链表的头结点，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode* headA, ListNode* headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
        ListNode *p1 = headA, *p2 = headB;
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == NULL) p1 = headB;
            else            p1 = p1->next;
            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == NULL) p2 = headA;
            else            p2 = p2->next;
        }
        return p1;
    }
};

另外一种思路是让 p1 和 p2 两个指针能够同时到达相交节点 ，那么可以通过预先计算两条链表的长度来做到这一点，具体代码如下：

/**
 * 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) {
        int lenA=0, lenB=0;
        // 计算两条链表的长度
        for(ListNode* p1 = headA; p1!=NULL; p1=p1->next)
            lenA++;
        for(ListNode* p2 = headB; p2!=NULL; p2=p2->next)
            lenB++;
        // 让p1和p2到达尾部的距离相同
        ListNode *p1 = headA, *p2 = headB;
        if(lenA > lenB){
            for(int i=0; i < lenA-lenB; i++)
                p1 = p1->next;
        }else{
            for(int j=0; j < lenB-lenA; j++)
                p2 = p2->next;
        }
        // 看两个指针是否会相同，p1 == p2 时有两种情况：
        // 1、要么是两条链表不相交，他俩同时走到尾部空指针
        // 2、要么是两条链表相交，他俩走到两条链表的相交点
        while(p1 != p2){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};