面试记录>链表大整数加法.ts

面试记录>链表大整数加法.ts

interface BigIntLinkList {
    next: BigIntLinkList | null;
    value: number
}

const reverseLinkListInPlace = (origin: BigIntLinkList) => {
    if (!origin.next) return origin
    let newOrigin = {
        next: null,
        value: origin.value
    }
    const worker = (alice: BigIntLinkList, bob: BigIntLinkList) => {
        if (bob.next === null) {
            bob.next = alice
            return bob
        }
        let newAlice = {
            next: alice,
            value: bob.value
        }
        return worker(newAlice, bob.next)
    }
    return worker(newOrigin, origin.next)
}

const add = (alice: BigIntLinkList, bob: BigIntLinkList) => {
    let charlie: BigIntLinkList = {
        value: 0,
        next: null
    }
    let curAlice = reverseLinkListInPlace(alice)
    let curBob = reverseLinkListInPlace(bob)
    let curCharlie = charlie
        
    for(let i = 1; i < 5; i++) {
        let sto = 0
        let temp = curAlice.value + curBob.value + sto
        if (temp > 9) {
            sto = 1
            curCharlie.value = Number(temp.toString().split().reverse()[0])
        } else {
            curCharlie.value = temp
        }
        curAlice = curAlice.next === null ? {value: 0, next: null} : curAlice.next
        curBob = curBob.next === null ? {value: 0, next: null} : curBob.next
        curCharlie.next = {
            value: 0,
            next: null
        }
        curCharlie = curCharlie.next
        if (curAlice.value === 0 && curBob.value === 0) break
    }
    printLinkList(reverseLinkListInPlace(charlie))
}

const printLinkList = (origin: BigIntLinkList) => {
    const output: number[] = []
    let cur = origin
    for(;;) {
        output.push(cur.value)
        if (cur.next) {
            cur = cur.next
        } else {
            break
        }
    }
    console.log(output.join('->'))
}

const node3: BigIntLinkList = {
    next: null,
    value: 3
}

const node2: BigIntLinkList = {
    next: node3,
    value: 2
}

const case1: any = {
    next: node2,
    value: 1
}

const node23: BigIntLinkList = {
    next: null,
    value: 6
}

const node22: BigIntLinkList = {
    next: node23,
    value: 5
}

const case2: any = {
    next: node22,
    value: 4
}

add(case1, case2)