Leetcode160. 相交链表(C++)

题目描述

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
      

这道题的思路很简单，我们以示例1为例：A链表比B链表长，如果都是从头结点各自每次一个的话A在公共的部分就会比B总是快一步，所以我们可以让B把它长出来的部分先走掉，这样做之后A与B同时走的话，就会在公共的部分相遇，示例1中第一次相遇的点就在value=8的结点。反之没有交点。

下面是我写的代码

/**
 * 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 a=0,b=0;
        ListNode *A=headA;//保存A链表的头结点
        ListNode *B=headB;//保存B链表的头结点
        while (A){ //计算A链表的长度
            a++;
            A=A->next;
        }
        while (B){ //计算B链表的长度
            b++;
            B=B->next;
        }
        A=headA;
        B=headB;
        int c=a-b;
        if (c>0){  //当A链表长与B链表，让A指针先走C步（比B长的长度）
            while (c){
                A=A->next;
                c--;
            }
        }else{
            while (c){ //当B链表长于A链表，让B指针先走C步（比A长的长度）
                B=B->next;
                c++;
            }
        }
        while (A!=B){  //A==B时就相遇了
            A=A->next;
            B=B->next;
        }
        return A;
    }
};