445. Add Two Numbers II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = 0;
        int len2 = 0;
        ListNode curr1 = l1;
        ListNode curr2 = l2;
        
        while (curr1 != null) {
            curr1 = curr1.next; 
            len1++;    
        }
        
        while (curr2 != null) {
            curr2 = curr2.next; 
            len2++;    
        }
            
        // 3->3->3 + 7->7 => 10->10->3
        curr1 = l1; 
        curr2 = l2;
        ListNode head = null;
        
        while (len1 > 0 && len2 > 0) {
            int sum = 0;
            
            if (len1 >= len2) {
                sum += curr1.val; 
                curr1 = curr1.next; 
                len1--;    
            }
            
            if (len1 < len2) {
                sum += curr2.val; 
                curr2 = curr2.next;
                len2--;    
            }
                
            ListNode curr = new ListNode(sum);
            curr.next = head;
            head = curr;    
        }

        // 10->10->3 --> 0->1->4 --> 4->1->0
        ListNode curr = head;
        head = null;
        int carry = 0;
        
        while (curr != null) {
            int sum = curr.val + carry;
            
            int val = sum % 10;
            carry = sum / 10;
            
            ListNode temp = new ListNode(val);
            temp.next = head;
            head = temp;
            curr = curr.next;    
        }
        
        if (carry != 0) {
            ListNode temp = new ListNode(carry);
            temp.next = head;
            head = temp;    
        }

        return head;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l1Rev = reverse(l1);
        ListNode l2Rev = reverse(l2);
        
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        
        int carry = 0;
        while(l1Rev != null || l2Rev != null) {
            int num1 = l1Rev == null ? 0 : l1Rev.val;
            int num2 = l2Rev == null ? 0 : l2Rev.val;
            
            int sum = num1 + num2 + carry;
            carry = sum / 10;
            int remain = sum % 10;
            curr.next = new ListNode(remain);
            curr = curr.next;
            
            if(l1Rev != null) l1Rev = l1Rev.next;
            if(l2Rev != null) l2Rev = l2Rev.next;
        }
        
        if(carry != 0) {
            curr.next = new ListNode(carry);
        }
        
        return reverse(dummy.next);
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        
        while(head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        
        return prev;
    }
}