Java教程

链表3——相交链表160

本文主要是介绍链表3——相交链表160，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

解法：双指针，空间复杂度O(1)

创建两个指针pA和pB，初始分别指向两个链表的头节点headA和headB，然后将两个指针依次遍历两个链表，如果某指针为空，则将指针移到另一个链表的链头，当两个指针都指向同一个节点或者null时，return。

正确性的证明：

（1）假设两个链表相交：

#1 不相交部分相等，则会同时到达两个链表相交的节点

#2 不相交部分不等，则在执行a+c+b次后，一定会在相交节点相遇

（2）假设两个链表不相交

#1 长度相等，则同时到达链尾，返回Null

#2 长度不等，则运行m+n次后，会返回Null

const getNode = (headA, headB) => {
    if (!headA || !headB)   return null;  // 链表为空，一定不相交

    let pa = headA, 
        pb = headB;
    while (pa !== pb) { 
        pa = (pa === null) ? headB : pa.next;  // 指针继续遍历 or 指向另外一条链表的链头
        pb = (pb === null) ? headA : pb.next;
    }
    return pa;  // null 或者 相交节点
}

这篇关于链表3——相交链表160的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航