链表3——相交链表160

2021/9/19 23:38:05

本文主要是介绍链表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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程