# 题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。题目数据保证整个链式结构中不存在环。

面试题 02.07. 链表相交 - 力扣（LeetCode）

# 分析

链表相交，则交点后链表相同，找到这个交点的指针即可。

首先让 curA 和 curB 分别指向 headA 和 headB，确认两链表长度，求差值使 curA 和 curB 位于离尾端距离相同的位置。

此时比较 curA 和 curB 是否相同，相同返回，不同都后移。

	// 时间复杂度：O (n + m)
	// 空间复杂度：O (1)
	class Solution {
	public:
	ListNode getIntersectionNode(ListNode headA, ListNode *headB) {
	ListNode* curA = headA;
	ListNode* curB = headB;
	int lenA = 0, lenB = 0;
	while (curA != NULL) { // 求链表 A 的长度
	lenA++;
	curA = curA->next;
	}
	while (curB != NULL) { // 求链表 B 的长度
	lenB++;
	curB = curB->next;
	}
	curA = headA;
	curB = headB;
	// 让 curA 为最长链表的头，lenA 为其长度
	if (lenB > lenA) {
	swap (lenA, lenB);
	swap (curA, curB);
	}
	// 求长度差
	int gap = lenA - lenB;
	// 让 curA 和 curB 在同一起点上（末尾位置对齐）
	while (gap--) {
	curA = curA->next;
	}
	// 遍历 curA 和 curB，遇到相同则直接返回
	while (curA != NULL) {
	if (curA == curB) {
	return curA;
	}
	curA = curA->next;
	curB = curB->next;
	}
	return NULL;
	}
	};

链表