两个链表的第一个公共节点|博客系列

/*
* 查找出两个链表的第一个公共节点
* params {ListNode} list1
* params {ListNode} list2
* returns {ListNode}
*/
function findFirstCommonNode(list1, list2) {
    if (!list1 || !list2) return null
    let length1 = getListNodeLength(list1)
    let length2 = getListNodeLength(list2)
    let diff, long, short; // 差值、较长链表、较短链表
    if (length1 > length2) {
        long = list1
        short = list2
        diff = length1 - length2
    } else {
        long = list2
        short = list1
        diff = length2 - length1
    }

    while (diff-- > 0) { // 较长链表先行diff步
        long = long.next
    }

    while (long) {
        if (long === short) { // 查找出相同项
            return long
        }
        long = long.next
        short = short.next
    }
    return null
}
// 获取链表的长度
function getListNodeLength(list) {
    let current = list
    let length = 0
    while (current) {
        current = current.next
        length++
    }
    return length
}

let common = {
    val: 1,
    next: {
        val: 2,
        next: null
    }
}
let l1 = {
    val: 4,
    next: {
        val: 3,
        next: common
    }
}
let l2 = {
    val: 3,
    next: common
}
console.log(findFirstCommonNode(l1, l2))
// { val: 1, next: { val: 2, next: null } }