LeetCode题2. 两数相加

题目描述： 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的， 并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 例子： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 思路： 1.遍历两个链表，节点相加并考虑这两个节点的前节点相加的进位， 2.使用递归 /** * 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 carry = 0 ; ListNode head = null ; ListNode tail = null ; 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 ; } } class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return recusive(l1, l2 , 0) ; } public ListNode recusive(ListNode l1 , ListNode l2, int carry){ if(l1 == null && l2 == null && carry == 0){ return null ; } int n1 = l1 == null ? 0 : l1.val ; int n2 = l2 == null ? 0 : l2.val ; int sum = n1 + n2 + carry ; ListNode node = new ListNode(sum % 10); node.next = recusive(l1 == null ? null : l1.next , l2 == null ? null : l2.next , sum / 10) ; return node ; } }