Skip to content

Instantly share code, notes, and snippets.

@riivanov
Last active March 30, 2024 04:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save riivanov/7b06d12830e1cbdec9c1ec8370e5065d to your computer and use it in GitHub Desktop.
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
// 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