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

题目要求

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

原文地址：https://blog.csdn.net/weixin_55341642/article/details/142748520

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！