[LeetCode力扣hot100]-链表

相交链表

160. 相交链表 - 力扣（LeetCode）

思路就是遍历两个链表，有相同的部分就可以视为相交。

但是长度不一样，比如两个会相交的链表，headA 的长度为 a + c，headB 的长度为 b + c，其中 c 是公共部分的长度。

指针pA遍历完后从headA跳转到headB，pB遍历完headB跳成A。

这样的话最后遍历a+b+c，肯定会最后同时到达相交节点的。

同理不相交的话会遍历a+b，最后会pA=pB=NULL，最后返回空

/** * 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) { if(headA==NULL||headB==NULL){ return NULL; } ListNode *a=headA; ListNode *b=headB;//定义指针 while(a!=b){ if(a==NULL){ a=headB; }else{ a=a->next; } if(b==NULL){ b=headA; }else{ b=b->next; } } return a; } };