单链表是否相交
程序员文章站
2024-03-16 15:30:28
...
方法一: 暴力法
对链表A中的每一个结点遍历 ,然后遍历整个链表 B,
并检查链表 B
中是否存在结点相同。
复杂度分析
- 时间复杂度 : (mn)(mn)。
- 空间复杂度 : O(1)O(1)。
方法二:哈希表法
遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点是否在哈希表中。若在,则为相交结点。
复杂度分析
- 时间复杂度 : O(m+n)O(m+n)。
- 空间复杂度 : O(m)O(m) 或 O(n)O(n)。
方法三:双指针法
创建两个指针 pA和 pB,分别初始化为链表 A
和 B
的头结点。然后让它们向后逐结点遍历。
当 pA 到达链表的尾部时,将它重定位到链表 B 的头结点 (你没看错,就是链表 B); 类似的,当pB到达链表的尾部时,将它重定位到链表 A 的头结点。若在某一时刻 pA 和 pB相遇,则 pA/pB为相交结点。
想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11},相交于结点 9。 由于 B.length (=4) < A.length (=6),pB 比 pA 少经过 2 个结点,会先到达尾部。将pB 重定向到 A 的头结点,pA 重定向到 B 的头结点后,pB 要比pA 多走 2 个结点。因此,它们会同时到达交点。
如果两个链表存在相交,它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时,记录下链表 A/B 对应的元素。若最后元素不相同,则两个链表不相交。
复杂度分析
- 时间复杂度 : O(m+n)O(m+n)。
- 空间复杂度 : O(1)O(1)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *p,*q;
p = headA;
q = headB;
while (p || q) {
if (p == q) {
return p; //交点
}
p = p ? p->next : headB; //若p走到A链尾,则重定向至headB
q = q ? q->next : headA; //若q走到B链尾,则重定向至headA
}
return NULL;