链表之差的绝对值-526互联

假设链表中每一个节点的值都在0-9之间，那么链表整体就可以代表一个非负整数。
给定两个这种链表，请生成代表两个整数之差绝对值结果链表。链表长度最大值为10000，链表任意值0≤val<9
要求:空间复杂度O(n)，时间复杂度O(n)
例如:链表1为9->3->7，链表2为9->6->3，最后生成新的结果链表为2-~>6,
不允许使用其它数据结构

实例1：
输入
{1,2,3},{4,5,6}
输出
{3,3,3}
实例2：
输入
{2,2,3},{2,2,7}
输出
{4}
实例3：
输入
{1,1,1},{1,1,1}
输出
{0}

代码示例

#include <iostream>
#include <string>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int value) : val(value), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* temp = cur;
        while(cur){
            temp = temp->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
}

void print_my(ListNode* pListHead1){
    ListNode* result = pListHead1;
    while (result) {
        std::cout << result->val << " ";
        result = result->next;
    }
    std::cout << std::endl;
}

ListNode* absolute_difference_list(ListNode* pListHead1, ListNode* pListHead2){
    ListNode* new1 = reverseList(pListHead1);
    ListNode* new2 = reverseList(pListHead2);

    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    int borrow = 0; // 借位值
    ListNode* l1 = new1;
    ListNode* l2 = new2;
    while (l1 || l2) {
        int x1 = l1 ? l1->val : 0;
        int x2 = l2 ? l2->val : 0;

        int diff = x1 - x2 - borrow;
        if (diff < 0) {
            borrow = 1;
            diff += 10;
        } else {
            borrow = 0;
        }
        cur->next = new ListNode(diff);
        cur = cur->next;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    // 处理最高位的借位
    if (borrow) {
        cur = head->next;
        while(cur && cur->val == 0) cur = cur->next;
        cur->val = 10 - cur->val;
        cur = cur->next;
        while(cur){
            cur->val = 9 - cur->val;
            cur = cur->next;
        }
    }
    head->next = reverseList(head->next);
    // 删除前置0
    ListNode* result = head;
    while (result && result->next && result->next->val == 0) {
        ListNode* temp = result->next;
        result->next = result->next->next;
        delete temp;
    }
    return head->next;;
}


ListNode* absolute_difference_list_LessLongLong(ListNode* pListHead1, ListNode* pListHead2){
    ListNode* new1 = reverseList(pListHead1);
    ListNode* new2 = reverseList(pListHead2);


    unsigned long long num1=0, num2=0;
    ListNode* cur = pListHead1;
    while(cur){
        num1 = num1 * 10 + cur->val;
        cur = cur->next;
    }
    cur = pListHead2;
    while(cur){
        num2 = num2 * 10 + cur->val;
        cur = cur->next;
    }
    unsigned long long res_temp = num1 > num2 ? num1-num2 : num2 -num1;
    string res_str = to_string(res_temp);
    ListNode* pHead = new ListNode(res_str[0]-'0');
    cur = pHead;
    for(size_t i=1;i<res_str.size();i++){
        cur->next = new ListNode(res_str[i]-'0');
        cur = cur->next;
    }
    return pHead;
}



int main() {
    ListNode* l1 = new ListNode(8);
    l1->next = new ListNode(0);
    // l1->next->next = new ListNode(3);

    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(1);
    l2->next->next = new ListNode(0);

    ListNode* result = absolute_difference_list(l1, l2);

    // // // Output result linked list: 3 -> 3 -> 3, representing integer 333
    while (result) {
        std::cout << result->val << " ";
        result = result->next;
    }


    return 0;
}