008、相交链表

0、题目描述

相交链表

1、法1

嵌套循环，从listA的第一个节点开始与listB的每个节点比对，有相同的就返回这个节点。
时间复杂度是n^2

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* pa = headA;struct ListNode* pb = headB;while (pa){pb = headB;while (pb){if (pa == pb){return pa;}pb = pb->next;}pa = pa->next;}return NULL;
}

2、法2

不用循环的方式找交点，如果双指针一起走的话，listA和listB的长度不同，容易错过交点位置。
所以先求listA和listB的长度，然后对齐一下，再双指针一起走就可以了。
如果有交点，尾节点一定是一样的，让长链表的指针先走一会儿，再齐头并进，就能找到交点。
如图，让listB的指针先走1下，就可以齐头并进了。lenB - lenA = 1

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{int lenA = 1;   int lenB = 1;struct ListNode* curA = headA;    struct ListNode* curB = headB;while (curA->next){curA = curA->next;lenA++;}while (curB->next){curB = curB->next;lenB++;}if (curA != curB)return NULL;else{//注意这里的条件LenA > lenB必须一样，在一样的条件下做出不一样的选择。struct ListNode* LongList = lenA > lenB ? headA : headB;struct ListNode* ShortList = lenA > lenB ? headB : headA;//abs是求绝对值的宏，这里的gap代表长度差int gap = abs(lenA - lenB);while (gap--){LongList = LongList->next;}//while (LongList->next){if (LongList == ShortList)break;LongList = LongList->next;ShortList = ShortList->next;}return LongList;}
}