剑指 Offer II 025. 链表中的两数相加

一句话概要

先反转链表，然后在从头开始加和进位。

题目

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

链接：https://leetcode.cn/problems/lMSNwu

思路

其实就是两个数字做加法。但是正常计算都是从右往左加和、进位，但是用链表表示一个数字，就只能从左往右去计算数字。所以先反转两个链表，然后一起移动加和，就可以了。

解法：先反转链表，再加和

代码

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;
}