Last active
March 30, 2024 04:00
-
-
Save riivanov/7b06d12830e1cbdec9c1ec8370e5065d to your computer and use it in GitHub Desktop.
reverse two linked lists, sum them and return the sum as a linked list
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// You are given two non-empty linked lists representing two non-negative integers. | |
// The digits are stored in reverse order, and each of their nodes contains a single digit. | |
// Add the two numbers and return the sum as a linked list. | |
// You may assume the two numbers do not contain any leading zero, except the number 0 itself. | |
// | |
// Example 1: | |
// | |
// Input: l1 = [2,4,3], l2 = [5,6,4] | |
// Output: [7,0,8] | |
// Explanation: 342 + 465 = 807. | |
// | |
// Example 2: | |
// | |
// Input: l1 = [0], l2 = [0] | |
// Output: [0] | |
// | |
// Example 3: | |
// | |
// Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] | |
// Output: [8,9,9,9,0,0,0,1] | |
// | |
// | |
// Constraints: | |
// | |
// The number of nodes in each linked list is in the range [1, 100]. | |
// 0 <= Node.val <= 9 | |
// It is guaranteed that the list represents a number that does not have leading zeros. | |
class Node { | |
constructor(public val: bigint = 0n, public next: Node = null) {} | |
} | |
function addTwoNumbers(l1: Node | null, l2: Node | null): Node | null { | |
const sum = toNumber(l1) + toNumber(l2); | |
const ary = toArray(sum).reverse(); | |
return toList(ary); | |
}; | |
function append(head: Node, node: Node) { | |
if (!head) { | |
head = new Node(); | |
} | |
let tmp = head; | |
while(tmp.next) { | |
tmp = tmp.next | |
} | |
tmp.next = node; | |
} | |
function toList(ary: Array<bigint>): Node | null { | |
if (!ary) return null; | |
const head = new Node(ary[0]); | |
for (let i = 1; i < ary.length; ++i) { | |
const next = new Node(ary[i]); | |
append(head, next) | |
} | |
return head; | |
} | |
function toArray(n: bigint): Array<bigint> { | |
return Array.from(String(n)).map(n => BigInt(n)); | |
} | |
// reverse list and create base 10 number | |
// from elements | |
function toNumber(ln: Node): bigint { | |
let rev = revValue(ln); | |
let len = 0n; | |
for (; !rev.next().done; ++len); | |
let pow = len - 1n; | |
let sum = 0n; | |
for (const digit of revValue(ln)) { | |
sum += BigInt(digit) * 10n ** pow; //Math.pow(10, pow) | |
pow--; | |
} | |
return sum; | |
} | |
// iterate backwards | |
function* revValue(ln: Node): Generator<number | null> { | |
const stack = [] | |
for (const val of value(ln)) { | |
stack.push(val); | |
} | |
while(stack.length > 0) { | |
yield stack.pop(); | |
} | |
return null; | |
} | |
// iterate forwards | |
function* value(ln: Node): Generator<bigint | null> { | |
if(ln.next) | |
{ | |
yield ln.val | |
yield* value(ln.next) | |
} | |
else yield ln.val | |
return null; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment