两个链表的第一个公共节点.md

题目描述

输入两个链表，找出它们的第一个公共结点。

解题思路

1. 先获取两个链表的长度length1和length2;
2. 判断出哪个链表更长一些并获取到长度的差值diff;
3. 让更长一点的链表先移动diff步,使得两个链表接下来移动的起点相同;
4. 两个链表一起移动, 判断出第一个相等的节点;

时间复杂度O(length1+length2) 空间复杂度O(0)

coding

/*
* 查找出两个链表的第一个公共节点
* 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 } }