相交链表--力扣160

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

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

思路

求两个链表的相交结点，使用双指针法，求出两个链表的长度的差值gap，让长的那一个链表先走gap步，使两个链表对齐，然后同时移动两个链表，直到找到相等的结点为止。

C++代码

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;//用于遍历的指针int lenA = 0;int lenB = 0;//两个链表的长度// 求链表A的长度while(curA != NULL) {lenA++;curA = curA->next;}// 求链表B的长度while (curB != NULL) { lenB++;curB = curB->next;}curA = headA;//返回开始位置curB = headB;if(lenA >= lenB){int gap = lenA -lenB;//两个链表的长度的差值while(gap--) curA = curA->next;while(curA != NULL){if (curA == curB) {return curA;}curA = curA->next;curB = curB->next;}}if(lenA < lenB){int gap = lenB - lenA;while(gap--) curB = curB->next;while(curB != NULL){if (curA == curB) {return curB;}curA = curA->next;curB = curB->next;}}  return NULL;}
};