一、问题描述
如下图所示
二、解题思路
方法一:双循环对比法
- 时间复杂度O（n^2） 空间复杂度O（1）
- 链表A中的节点依次与链表B中的每个节点比较
- 若出现节点相同，则相交且为第一个交点
- 若链表A走到空依然没有相同的节点，则不相交
注意：暴力解法效率较低，不建议采用
方法二: 双指针法
- 时间复杂度O（n) 空间复杂度O（1）
- 首先遍历链表求出两个链表的长度，求得长度的差值
- 定义两个快慢指针，哪个链表长，快指针就指向哪个链表
- 两个指针分别从两个链表的第一个节点开始遍历，快指针先走出一个长度差值，之后两个指针每移动一步，比较指向的节点是否相同
- 若出现节点相同，则相交且为第一个交点
- 若两个指针走到空依然没有相同的节点，则不相交
三、C语言代码实现
方法一实现代码
struct ListNode { int val; struct ListNode *next; }; typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode*pcurA=headA; ListNode*pcurB=headB; while(pcurA) { pcurB=headB; while(pcurB) { if(pcurA==pcurB) return pcurA; pcurB=pcurB->next; } pcurA=pcurA->next; } return NULL; }
方法二实现代码
struct ListNode { int val; struct ListNode *next; }; typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode*pcurA=headA; ListNode*pcurB=headB; int countA=0; int countB=0; while(pcurA)//求出链表长度 { pcurA=pcurA->next; countA++; } while(pcurB) { pcurB=pcurB->next; countB++; } int tmp=abs(countA-countB);//长度差值 ListNode*slow,*fast; if(countA<countB) { slow=headA; fast=headB; } else { slow=headB; fast=headA; } while(tmp--)//长链表先走差值的步数 { fast=fast->next; } while(fast&&slow)//同步比较 { if(fast==slow) return fast; fast=fast->next; slow=slow->next; } return NULL; }
