2. 两数相加 - 力扣（LeetCode）

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int val=0, ListNode next=null) {*         this.val = val;*         this.next = next;*     }* }*/
public class Solution {public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {int carry = 0;ListNode head = null, tail = null;while(l1 != null || l2 != null){int n1 = l1 == null ? 0 : l1.val;int n2 = l2 == null ? 0 : l2.val;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;}
}

• 时间复杂度：O(max⁡(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
• 空间复杂度：O(1)。注意返回值不计入空间复杂度。