首页 > 代码库 > Add Two Numbers

Add Two Numbers

2024-07-02 09:38:37   231人阅读

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 

Recursive-Code

 1 //using global variable in the recursion is not graceful
 2     //I prefer to use a help_function
 3     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 4         return addTwoNumbers_helper(l1, l2, 0);
 5     }
 6 
 7     public ListNode addTwoNumbers_helper(ListNode l1, ListNode l2, int carry) {
 8         if (l1 == null && l2 == null) {
 9             //here we need to handle the carry
10             if (carry == 0)
11                 return null;
12             else {
13                 ListNode a = new ListNode(carry);
14                 return a;
15             }
16 
17         }
18         int first = 0, second = 0;
19         if (l1 != null)
20             first = l1.val;
21         if (l2 != null)
22             second = l2.val;
23         ListNode result = new ListNode((first + second + carry) % 10);
24         carry = (first + second + carry) / 10;
25         result.next = addTwoNumbers_helper(l1 == null ? null : l1.next,
26                 l2 == null ? null : l2.next, carry
27         );
28         return result;
29 
30     }

 

Non-recursive

 1 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 2         if (l1 == null && l2 == null)
 3             return null;
 4         int first = l1.val;
 5         int second = l2.val;
 6 
 7         ListNode l3 = new ListNode((first + second) % 10);
 8         ListNode output = l3;
 9         int carry = (first + second) / 10;
10         l1 = l1.next;
11         l2 = l2.next;
12         //at this point, the list node may be null,
13         //pay attention to the null condition
14         while (l1 != null || l2 != null) {
15             if (l1 == null)
16                 first = 0;
17             else {
18                 first = l1.val;
19                 l1 = l1.next;
20             }
21             if (l2 == null) {
22                 second = 0;
23             } else {
24                 second = l2.val;
25                 l2 = l2.next;
26             }
27             l3.next = new ListNode((first + second + carry) % 10);
28             carry = (first + second + carry) / 10;
29             l3 = l3.next;
30         }
31         //don‘t forget the carry
32         if (carry != 0)
33             l3.next = new ListNode(carry);
34         return output;
35     }

 


联系
我们