/**
 * @Author :田宇寒.
 * @Date :Created in 14:19 2021年5月28日
 * @Description:leetcode2题 两数和 链表进位
 * @Modified By:
 * @Version: 1.0$
 */

public class code2 {
 /**
 * Definition for singly-linked list.
 */
 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 upgrade = 0;
 int a = 0;
 int b = 0;
 ListNode result = new ListNode();
 ListNode temp = result;
 while (l1 != null || l2 != null || upgrade > 0) {
 a = l1 == null? 0 : l1.val;
 b = l2 == null? 0 : l2.val;
 temp.val = (a + b + upgrade) % 10 ;
 if ((a + b + upgrade) >= 10) {
 upgrade = 1;
 } else {
 upgrade = 0;
 }
 if (l1 != null) {
 l1 = l1.next;
 }
 if (l2 != null) {
 l2 = l2.next;
 }
 if (l1 != null || l2 != null || upgrade > 0) {
 temp.next = new ListNode(0);
 temp = temp.next;
 }
 }
 return result;
 }
 }

 class SolutionStandard {
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 /**
 * create by: 田宇寒
 * description: 官网标准写法 时间复杂度为 O(max(m,n)) 空间复杂度O(1)
 * create time: 14:28 2021年5月28日
 * @Param: l1
 * @Param: l2
 * @return code2.ListNode
 */
 ListNode head = null, tail = null;
 int carry = 0;
 while (l1 != null || l2 != null) {
 int n1 = l1 != null ? l1.val : 0;
 int n2 = l2 != null ? l2.val : 0;
 int sum = n1 + n2 + carry;
 if (head == null) {
 head = tail = new ListNode(sum % 10);
 } else {
 tail.next = new ListNode(sum % 10);
 tail = tail.next;
 }
 carry = sum / 10;
 if (l1 != null) {
 l1 = l1.next;
 }
 if (l2 != null) {
 l2 = l2.next;
 }
 }
 if (carry > 0) {
 tail.next = new ListNode(carry);
 }
 return head;
 }
 }

}