LeetCode Link: 445. Add Two Numbers II
Language: C#
Problem Statement
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Examples
Example 1:
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]
Example 3:
Input: l1 = [0], l2 = [0]
Output: [0]
Constraints
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
Solution
/**
* 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)
{
var r1 = Reverse(l1);
var r2 = Reverse(l2);
var r3 = Add(r1, r2);
return Reverse(r3);
}
private ListNode Add(ListNode l1, ListNode l2)
{
ListNode res = null;
ListNode head = null;
var rem = 0;
while (l1 != null && l2 != null)
{
var val = l1.val + l2.val + rem;
rem = val > 9 ? 1 : 0;
val = val > 9 ? (val - 10) : val;
if (res == null)
{
res = new ListNode();
head = res;
}
else
{
res.next = new ListNode();
res = res.next;
}
res.val = val;
l1 = l1.next;
l2 = l2.next;
}
while (l1 != null)
{
res.next = new ListNode();
res = res.next;
res.val = l1.val + rem;
rem = res.val > 9 ? 1 : 0;
res.val = res.val > 9 ? (res.val - 10) : res.val;
l1 = l1.next;
}
while (l2 != null)
{
res.next = new ListNode();
res = res.next;
res.val = l2.val + rem;
rem = res.val > 9 ? 1 : 0;
res.val = res.val > 9 ? (res.val - 10) : res.val;
l2 = l2.next;
}
if (rem == 1)
{
res.next = new ListNode();
res.next.val = 1;
}
return head;
}
private ListNode Reverse(ListNode l)
{
if (l == null || l.next == null)
{
return l;
}
var next = l.next;
l.next = null;
var head = Reverse(next);
next.next = l;
return head;
}
}
Complexity
Time Complexity: O(N)
Space Complexity: O(N)