当前位置：首页 > news >正文

【单链表算法实战】解锁数据结构核心谜题——相交链表

news 2025/6/28 13:35:01

题目如下：

在这里插入图片描述

解题过程如下：

相交链表只可以在中间任意位置/头/尾结点相交，如下图：

在这里插入图片描述

一个next指针只能指向一块地址，所以不会出现这种情况：
在这里插入图片描述

在返回相交链表的起始结点之前先要判断两个链表是否相交，分析下列两种方法是否可行？

遍历两个链表，判断结点（地址）是否相同。如果像示例1一样，两个链表的长度不等，代码运行结果就是两个链表不会相交，这与事实恰恰相反。所以这个方法不可行：
看两个链表的尾结点（地址）是否相同。参考相交链表的三种情况，尾结点相同那么两个链表就一定相交。

那么怎么返回相交链表的起始结点呢？

思路：求两个链表的长度，长链表先走长度差步，长短链表遍历比较结点的地址是否相同。

完整代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//求两个链表的长度ListNode* pa = headA;ListNode* pb = headB;int sizeA = 0;int sizeB = 0;while (pa){++sizeA;pa = pa->next;}while (pb){++sizeB;pb = pb->next;}//长链表先走长度差（gap）步int gap = abs(sizeA - sizeB);ListNode* shortList = headA;ListNode* longList = headB;//假设B是长链表if (sizeA > sizeB){shortList = headB;longList = headA;}while (gap--){longList = longList->next;}//长短链表遍历结点的地址是否相同while (longList) //等同于shortList != NULL{if (longList == shortList)return longList;longList = longList->next;shortList = shortList->next;}return NULL;
}