Linked list: adding numbers in the linked list

subject

Their thinking

• Method 1 ：

The length of two linked lists may be different , Convert the linked list nodes into integers , Then add integers , Finally, the sum obtained is reduced to a linked list . But when you add integers , Integer overflow may occur . So this method is not feasible .

• Method 2 ：
  Reverse a linked list , Align the two tails of the original linked list , That is, we can start with single digits , Add digit by digit . Finally, restore the inverted linked list .

The specific code is as follows ：

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) {
    
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        return reverseList(addReversed(l1, l2));
    }

    private ListNode addReversed(ListNode reverseL1, ListNode reverseL2) {
    
        int carry = 0;
        ListNode dummy =  new ListNode(0);
        ListNode sumNode = dummy;
        while(reverseL1 != null || reverseL2 != null) {
    
            int sum =   (reverseL1 == null ? 0 : reverseL1.val) + (reverseL2 == null ? 0 : reverseL2.val) + carry;
  
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum; 

            ListNode newNode = new ListNode(sum);
            sumNode.next = newNode;
            sumNode = sumNode.next;
            reverseL1 = reverseL1 == null ? null : reverseL1.next;
            reverseL2 = reverseL2 == null ? null : reverseL2.next;
        }
        if(carry > 0) {
    
            sumNode.next = new ListNode(carry);
        }
  
        return dummy.next;
    }

    private ListNode reverseList(ListNode head){
    
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
    
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

summary

Add the numbers in the linked list , You can use the characteristics of the reverse linked list , Add from the single digits of the number .