Subtract Two Numbers represented as Linked Lists Hard 0 attempts
GeeksforGeeks ↗

Subtract Two Numbers represented as Linked Lists

Hard Linked List GeeksforGeeks

You're given two numbers, each represented as a linked list of digits. Digits are stored most significant first. Subtract the smaller number from the larger one and return the non-negative result in the same order, without leading zeros except for a single zero node when the numbers are equal.

Input Format
Implement subtractLists(l1, l2). Inputs below show JavaScript function arguments; there is no stdin parsing. Linked lists use value arrays. The editor passes nodes with val and next properties; [] becomes null.
Output Format
Return the result described in the statement. Returned list heads are displayed as value arrays; a null head is [].

Sample Input and Output

Example 1 · Run Sample

Input
l1 = [1,0,0]
l2 = [1]
Output
[9,9]

Example 2

Input
l1 = [1]
l2 = [1]
Output
[0]
Constraints
  • 1 to 10^4 nodes per list
Test Cases (2)
Case 1
Args: [[1,0,0],[1]] Expected: [9,9]
Case 2
Args: [[1],[1]] Expected: [0]
Topics
Linked List

Exact BigInt Subtraction

javascript
function subtractLists(l1, l2) {
  function toNum(l) { let n = 0n; while (l) { n = n*10n + BigInt(l.val); l = l.next; } return n; }
  let diff = toNum(l1) - toNum(l2);
  if (diff < 0n) diff = -diff;
  const s = diff.toString(); let head = null, tail = null;
  for (const c of s) {
    const node = {val: parseInt(c), next: null};
    if (!head) head = tail = node; else { tail.next = node; tail = node; }
  }
  return head || {val: 0, next: null};
}

Time: O(m² + n²) as a loose bound when accounting for growing BigInt arithmetic | Space: O(max(m,n))

Saved in this browser only. Private to you.

JavaScript