数据结构 ——— 单链表oj题：相交链表（链表的共节点）

目录

题目要求

手搓两个相交简易链表

代码实现 

---

题目要求

两个单链表的头节点 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)