夯实C++基础之刷题：链表——相交链表

一点点进步计划：首先要坚持刷题，刷题是一个将思路用代码实现的过程；2要自己看知识点 平时也看看面经 这样才与时俱进//-------先从每天能做一道题开始把

题目

1、相交链表

2、思路

看问题解析都用到了数学的双指针的方法，我是想不明白，但看解题的意思是说只要出现一个相同的元素了，后面的元素就会相交，不存在两个链表只相交一个然后就岔开的情况
所以我的思路是：既然后面的一定是一样的，那从尾端对其，直接比较后半部分就可以了，让长的那个链表先走完长的那部分
1、首先要判空，有一个为空，那肯定返回0
2、写一个函数获取链表的长度，让长的走完长的那部分
3、尾端对齐后，找到第一个相同的元素，就找到了交点，任何一个为空了就代表没有交点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */


 int getLength(ListNode* headA)
 {
     int n = 0;
     while(headA)
     {
         n++;
         headA = headA->next;
     }
     return n;
 }

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //这个题目有一层意思是说 只要有一个相同了 则后面的都会相同
        if(!headA || !headB) return 0;
        int lenA =getLength(headA);
        int lenB =getLength(headB);
        //先把差距走完
        if(lenA>lenB)
        {
            for(int i = 0; i<lenA-lenB; i++) headA = headA->next;
        }else
        {
            for(int i = 0; i<lenB-lenA; i++) headB = headB->next;
        }
        //一样的长度了，找到相同的就行
        while(headA && headB && headA!=headB)
        {
            headA = headA->next;
            headB = headB->next;
        }
        //要么有了要么没有了
        return (headA&&headB) ? headA : 0;

    }
};

 /*
 class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return 0;
        while(headA->next) headA = headA->next;
        while(headB->next) headB = headB->next;
        //都走到最后一个再往前对比 第一个不一样的就是相交的点  但没有前指针所以没有办法往前走
        
    }
};
 */