数据结构 ——— 相交链表（链表的共节点）

题目要求

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

---

手搓两个相交简易链表

代码演示：

struct ListNode* a1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(a1);
struct ListNode* a2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(a2);

a1->val = 1;
a2->val = 2;

a1->next = a2;

struct ListNode* b1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(b1);
struct ListNode* b2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(b2);
struct ListNode* b3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(b3);

b1->val = 1;
b2->val = 2;
b3->val = 3;

b1->next = b2;
b2->next = b3;

struct ListNode* c1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(c1);
struct ListNode* c2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(c2);
struct ListNode* c3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(c3);

c1->val = 1;
c2->val = 2;
c3->val = 3;

a2->next = c1;
b3->next = c1;
c1->next = c2;
c2->next = c3;
c3->next = NULL;

---

代码实现

代码演示：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
	// 先找各自链表的尾节点，判断是否相交
	struct ListNode* tailA = headA;
	struct ListNode* tailB = headB;

	int lenA = 1;
	int lenB = 1;

	while (tailA->next != NULL)
	{
		tailA = tailA->next;
		lenA++;
	}

	while (tailB->next != NULL)
	{
		tailB = tailB->next;
		lenB++;
	}

	if (tailA != tailB)
		return NULL;

	// 找相交节点
	int gap = abs(lenA - lenB);

	struct ListNode* longList = headA;
	struct ListNode* shortList = headB;

	if (lenA < lenB)
	{
		longList = headB;
		shortList = headA;
	}

	while (gap--)
	{
		longList = longList->next;
	}

	while (longList != shortList)
	{
		longList = longList->next;
		shortList = shortList->next;
	}

	return longList;
}

代码解析：

代码思路：先判断两个链表是否相交，那么就是看尾节点是否相同，不相同就说明不相交，返回NULL 即可，尾节点相同则表示相交，再将节点长的链表走差距步，然后再同时往后走，找到相同的节点时，就是相交的节点

代码逻辑：两个链表各自往后走，并记录各自节点的个数，先判断尾节点的地址是否相同（注意：不是判断两个节点的数据是否相同），不想同就返回 NULL ，相同就利用 abs 函数求出 lenA 减去 lenB 的绝对值，就是两个链表相差的节点个数，再求出长的链表，先走差距步，再一起往后走，走到地址相同的节点时，就时交点

代码验证：

算法的时间和空间复杂度：

3 个 while 循环执行了 N 次，也就是 3*N（除去 3） ，且没有产生额外的空间

时间复杂度： O(N)

空间复杂度：O(1)