[数据结构与算法]02.07. 链表相交

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

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

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

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

方法1：朴素算法

/**
 * 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) {
        //注意：这个题是节点相等，不是节点值相等。
		ListNode *curA = headA;
        ListNode *curB = headB;
        if(curA == NULL || curB == NULL) return NULL;
        //先要算出他们之间的长度
        int len1 = 0;
        while(curA){
            len1++;
            curA = curA->next;
            
        }
        int len2 = 0;
        while(curB){
            len2++;
            curB = curB->next;
            
        }
        //关键点，之前移动到末尾了，需要重新开始
        curA = headA;
        curB = headB;
        //长度不一样，让curA为最长链表的头，len1为其长度
        if(len1<len2){
            swap(len1,len2);
            swap(curA,curB);
        }
        int size = len1-len2;
        while(size--){
            curA = curA->next;
        }

        while(curA)
        {
            if(curB == curA){//这里要先比，在往下移动，不然忽略第一个
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }

        return NULL;
    }
};

方法2：双指针

/**
 * 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) {
        //双指针
        ListNode *curA = headA;
        ListNode *curB = headB;
        while(curA != curB)
        {
            //走完自己的路再走别人走过的路，看看是否能相遇
            curA = curA != NULL?curA->next:headB;//关键点是换头节点
            curB = curB != NULL?curB->next:headA;
        }

        return curA;
    }
};