Linklist经典题目—判断两个链表是否有相交并返回相交起始结点(附数学推导) 数据结构数据结构与算法

本文内容

相交链表问题的解决思路及数学原理推导
可执行代码

题目内容
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。图例如下：

文章图片

【Linklist经典题目—判断两个链表是否有相交并返回相交起始结点(附数学推导)】题目作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetb...
题目来源：力扣（LeetCode）
题解作者:WildDuck
解决思路与原理
本题目与判断环形链表以及其入口同类型，不仅解决上用到双指针，本质上也同为路程问题

文章图片

文章图片

2.可执行代码，双指针构建相同路程解决问题

/** * Definition for singly-linked list. * struct ListNode { *int val; *struct ListNode *next; * }; */ typedef struct ListNode* ListNode_pointer; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode_pointer temp_A = headA; ListNode_pointer temp_B = headB; while(temp_A != temp_B) { if(temp_A != NULL && temp_B != NULL) { temp_A = temp_A -> next; temp_B = temp_B -> next; } else if(temp_A == NULL) { temp_A = headB; } else if(temp_B == NULL) { temp_B = headA; } } return temp_A; }