Sword finger offer II 025 Adding two numbers in a linked list

A word summary

First reverse the list , Then add and carry from the beginning .

subject

Given two Non empty linked list l1 and l2 To represent two nonnegative integers . The highest digit is at the beginning of the list . They store only one digit per node . Adding these two numbers will return a new linked list .

It can be assumed that in addition to numbers 0 outside , Neither of these numbers starts with zero .

link ：https://leetcode.cn/problems/lMSNwu

Ideas

It's actually adding two numbers . But the normal calculation is to add the sum from right to left 、 carry , But using a linked list to represent a number , You can only calculate numbers from left to right . So first reverse the two linked lists , Then move the sum together , That's all right. .

solution ： First reverse the list , Add the sum

Code

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
    l1 = reverseList(l1);
    l2 = reverseList(l2);
    ListNode next = null;
    int add = 0;
    while (l1 != null || l2 != null) {
    
        int sum = add;
        if (l1 != null) {
    
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
    
            sum += l2.val;
            l2 = l2.next;
        }
        add = sum / 10;
        ListNode current = new ListNode(sum % 10);
        current.next = next;
        next = current;
    }
    if (add != 0) {
    
        ListNode current = new ListNode(add);
        current.next = next;
        return current;
    }
    return next;
}


public ListNode reverseList(ListNode head) {
    
    ListNode current = head;
    ListNode pre = null;
    ListNode next;
    while (current != null) {
    
        next = current.next;
        current.next = pre;
        pre = current;
        current = next;
    }

    return pre;
}