Problem statement

Two non-negative integers are stored in linked lists head1 and head2, one decimal digit per node, with the most significant digit first. The lists may have different lengths and may start with leading zeros.

Subtract the smaller number from the larger one and return the difference as a linked list in the same form, but without leading zeros. If the two numbers are equal, return a single node 0.

Example 1

Input: head1 = [1,0,0], head2 = [1,2]
Output: [8,8]
Explanation: 100 - 12 = 88.

Example 2

Input: head1 = [0,0,6,3], head2 = [7,1,0]
Output: [6,4,7]
Explanation: The first number is 63 once its leading zeros are dropped, so the larger is 710: 710 - 63 = 647.

Example 3

Input: head1 = [4,5], head2 = [4,5]
Output: [0]
Explanation: Equal numbers give 0.

Constraints

• 1 <= number of nodes in each list <= 10^4
• 0 <= Node.val <= 9

Hints for Subtraction in Linked List

1. Hint 1

   First decide which number is larger. Leading zeros make list length a misleading guide — strip them before comparing.

2. Hint 2

   After stripping, the longer number is larger; with equal lengths, the first differing digit from the front decides.

3. Hint 3

   Subtract digit by digit from the least significant end with a borrow, then remove the leading zeros the subtraction leaves behind (keep one digit if the result is 0).

How to solve Subtraction in Linked List

This is grade-school subtraction on digit sequences. The only list-specific work is that digits are stored most significant first, so read each list into an array (or reverse it) to subtract from the right, and handle leading zeros on both the inputs and the result.

Approach

1. Read each list's digits and drop leading zeros, keeping at least one digit.
2. Make a the larger number: the longer sequence, or on equal length the one with the larger first differing digit.
3. Walk both from the least significant digit: d = a[i] - borrow - (b's digit or 0); if d < 0 add 10 and set borrow = 1, otherwise borrow = 0.
4. Drop leading zeros from the result (keep one), and build the output list most significant digit first.

Why it works

Subtracting the smaller from the larger never needs a final borrow, so the column method yields the exact difference. Comparing after stripping leading zeros is correct because then the number of digits is the order of magnitude.

Complexity

• Time — O(n + m)
• Space — O(n + m)

Pitfalls

• Comparing raw lengths: 0063 has four nodes but is smaller than 710.
• Numbers have up to 10^4 digits — no built-in integer type holds them.
• Equal numbers produce all zeros; the answer is the single node 0, not an empty list.

Reference solution

Python

from typing import Optional

def digits_of(h):
    d = []
    while h:
        d.append(h.val)
        h = h.next
    i = 0
    while i < len(d) - 1 and d[i] == 0:
        i += 1
    return d[i:]

def subLinkedList(head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
    a, b = digits_of(head1), digits_of(head2)
    if len(a) < len(b) or (len(a) == len(b) and a < b):
        a, b = b, a
    res, borrow, j = [], 0, len(b) - 1
    for i in range(len(a) - 1, -1, -1):
        d = a[i] - borrow - (b[j] if j >= 0 else 0)
        j -= 1
        borrow = 1 if d < 0 else 0
        res.append(d + 10 if d < 0 else d)
    while len(res) > 1 and res[-1] == 0:
        res.pop()
    head = None
    for d in res:  # least significant first, so prepending puts the top digit at the head
        head = ListNode(d, head)
    return head

Java

static int[] digitsOf(ListNode h) {
    ArrayList<Integer> d = new ArrayList<>();
    for (; h != null; h = h.next) d.add(h.val);
    int i = 0;
    while (i < d.size() - 1 && d.get(i) == 0) i++;
    int[] out = new int[d.size() - i];
    for (int t = i; t < d.size(); t++) out[t - i] = d.get(t);
    return out;
}

public static ListNode subLinkedList(ListNode head1, ListNode head2) {
    int[] a = digitsOf(head1), b = digitsOf(head2);
    boolean swap = a.length < b.length;
    if (a.length == b.length) {
        for (int t = 0; t < a.length; t++) if (a[t] != b[t]) { swap = a[t] < b[t]; break; }
    }
    if (swap) { int[] tmp = a; a = b; b = tmp; }
    int[] res = new int[a.length];
    int borrow = 0, len = 0;
    for (int i = a.length - 1, j = b.length - 1; i >= 0; i--, j--) {
        int d = a[i] - borrow - (j >= 0 ? b[j] : 0);
        borrow = d < 0 ? 1 : 0;
        res[len++] = d < 0 ? d + 10 : d;
    }
    while (len > 1 && res[len - 1] == 0) len--;
    ListNode head = null;
    for (int r = 0; r < len; r++) head = new ListNode(res[r], head);
    return head;
}

C++

vector<int> digitsOf(ListNode* h) {
    vector<int> d;
    for (; h; h = h->next) d.push_back(h->val);
    size_t i = 0;
    while (i + 1 < d.size() && d[i] == 0) i++;
    return vector<int>(d.begin() + i, d.end());
}

ListNode* subLinkedList(ListNode* head1, ListNode* head2) {
    vector<int> a = digitsOf(head1), b = digitsOf(head2);
    if (a.size() < b.size() || (a.size() == b.size() && a < b)) swap(a, b);
    vector<int> res;
    int borrow = 0;
    for (int i = (int)a.size() - 1, j = (int)b.size() - 1; i >= 0; i--, j--) {
        int d = a[i] - borrow - (j >= 0 ? b[j] : 0);
        borrow = d < 0 ? 1 : 0;
        res.push_back(d < 0 ? d + 10 : d);
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    ListNode* head = nullptr;
    for (int d : res) head = new ListNode(d, head);
    return head;
}

JavaScript

var digitsOf = function(h) {
    var d = [];
    for (; h !== null; h = h.next) d.push(h.val);
    var i = 0;
    while (i < d.length - 1 && d[i] === 0) i++;
    return d.slice(i);
};

var subLinkedList = function(head1, head2) {
    var a = digitsOf(head1), b = digitsOf(head2);
    var swap = a.length < b.length;
    if (a.length === b.length) {
        for (var t = 0; t < a.length; t++) if (a[t] !== b[t]) { swap = a[t] < b[t]; break; }
    }
    if (swap) { var tmp = a; a = b; b = tmp; }
    var res = [], borrow = 0, j = b.length - 1;
    for (var i = a.length - 1; i >= 0; i--, j--) {
        var d = a[i] - borrow - (j >= 0 ? b[j] : 0);
        borrow = d < 0 ? 1 : 0;
        res.push(d < 0 ? d + 10 : d);
    }
    while (res.length > 1 && res[res.length - 1] === 0) res.pop();
    var head = null;
    for (var r = 0; r < res.length; r++) head = new ListNode(res[r], head);
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• GCD Sort of an Array Hard
• Count Valid Paths in a Tree Hard
• Create Components With Same Value Hard
• Cat and Mouse Hard
• Find the Number of Subsequences With Equal GCD Hard
• Find the Count of Monotonic Pairs I Hard