Sponsored
Sponsored
This approach involves iterating through both linked lists, node by node, adding corresponding values along with any carry from the previous addition. The result at each step is appended to a new linked list. If one list is longer than the other, the iteration continues on the longer list alone. A final check is done to handle any remaining carry.
Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists. This is because we iterate through each node exactly once.
Space Complexity: O(max(m, n)) to store the resulting list.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
12 ListNode dummy = new ListNode(0);
13 ListNode current = dummy;
14 int carry = 0;
15 while (l1 != null || l2 != null) {
16 int x = (l1 != null) ? l1.val : 0;
17 int y = (l2 != null) ? l2.val : 0;
18 int sum = carry + x + y;
19 carry = sum / 10;
20 current.next = new ListNode(sum % 10);
21 current = current.next;
22 if (l1 != null) l1 = l1.next;
23 if (l2 != null) l2 = l2.next;
24 }
25 if (carry > 0) {
26 current.next = new ListNode(carry);
27 }
28 return dummy.next;
29 }
30}C# uses similar logic to ensure that carry and nodes are handled properly. Initialized a dummy ListNode to help with linking and cycle through nodes while adding corresponding values with carry management.
The recursive approach solves the problem by recursing down the linked lists, accumulating values with carry and constructing the result linked list from the returned values from child calls. Each recursive call processes one pair of nodes from the lists, similar to how you would process each position in a sum independently in the iterative version.
Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n)) because of the recursion stack.
1 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) {
return AddTwoNumbersRecursive(l1, l2, 0);
}
private ListNode AddTwoNumbersRecursive(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry == 0) return null;
int sum = carry;
if (l1 != null) sum += l1.val;
if (l2 != null) sum += l2.val;
ListNode result = new ListNode(sum % 10);
result.next = AddTwoNumbersRecursive(l1 != null ? l1.next : null, l2 != null ? l2.next : null, sum / 10);
return result;
}
}The recursive approach in C# mirrors Java's solution. It uses a helper method to process sum, manage carry, create new nodes, and handle further list traversal recursively until sums are complete.