欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表是否相交

程序员文章站 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;