Home Computer Science Java Algorithm

221 · Add Two Numbers II - LintCode

# Description

You have two numbers represented by linked list, where each node contains a single digit. The digits are stored in forward order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example

Example 1:

Input: 6->1->7   2->9->5
Output: 9->1->2

Example 2:

Input: 1->2->3   4->5->6
Output: 5->7->9

# Solution

和 Lintcode167-addTwoNumbers 相似，是 ListNode 是 forward 開始算，要把 l1,l2 和答案都 reverse

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param l1: The first list.
     * @param l2: The second list.
     * @return: the sum list of l1 and l2.
     */
    public ListNode addLists2(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        return reverse(addTwoList(l1, l2));
    }
    private ListNode reverse(ListNode l){
        ListNode cur = l;
        ListNode prev = null;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    private ListNode addTwoList(ListNode l1, ListNode l2){
        if (l1 == null || l2 == null) return null;
        ListNode head = new ListNode(-1);
        ListNode point = head;
        int carry = 0;
        while (l1 != null && l2 != null){
            int sum = l1.val + l2.val + carry;
            point.next = new ListNode(sum % 10);
            carry = sum / 10;
            point = point.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        while (l1 != null){
            int sum = l1.val + carry;
            point.next = new ListNode(sum % 10);
            carry = sum / 10;
            point = point.next;
            l1 = l1.next;
        }
           while (l2 != null){
            int sum = l2.val + carry;
            point.next = new ListNode(sum % 10);
            carry = sum / 10;
            point = point.next;
            l2 = l2.next;
        }
        if(carry > 0){
            point.next = new ListNode(carry);
        }
        return head.next;
    }
}