給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)纤垂。
其中夕晓，它們各自的位數(shù)是按照 逆序 的方式存儲的宛乃，并且它們的每個節(jié)點(diǎn)只能存儲 一位 數(shù)字。
如果，我們將這兩個數(shù)相加起來征炼，則會返回一個新的鏈表來表示它們的和析既。
您可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭谆奥。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
先了解了下ListNode：
?*?Definition?for?singly-linked?list.
?*?public?class?ListNode?{
?* ? ? ? ? ? public?int?val;
?* ? ? ? ? ? public?ListNode?next; ? //鏈表指向的下一個值的指針
?* ? ? ? ? ? public?ListNode(int?x)?{?val?=?x;?}?//賦值
?*?}
定義鏈表ListNode時眼坏，
1. 鏈表的首個值不能為0，當(dāng)首個參數(shù)為0時酸些，代表著鏈表為空宰译。
2. 只需要定義一個ListNode xx = new ListNode(0);即可。即只定義一個空鏈表擂仍。
3. 不需要定義長度 囤屹。
賦值時，
1. 通過xx.next = new ListNode(4);來賦值逢渔，注意此時是賦值給下一個指針指向的位置,此時此鏈表一個值肋坚，值為4。
2. 通過一個鏈表指向原鏈表地址肃廓，賦值完成時智厌，打印原鏈表的指針地址，獲取所有值盲赊。
取值時铣鹏，
1. 取第一個值時，只需要xx.val即可哀蘑。
2. 取第二或之后的值時诚卸，需要xx = xx.next;int x = xx.val;這個方式取值。
解題：? 時間復(fù)雜度：O(max(m,n))? m 和 n 分別表示 l1 和 l2 的長度
執(zhí)行用時：152 ms ? 內(nèi)存消耗：27.7 MB
? ? public class Solution
? ? {
? ? ? ? public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
? ? ? ? {
? ? ? ? ? ? int val = 0;
? ? ? ? ? ? ListNode prenode = new ListNode(0);? // 初始化
? ? ? ? ? ? ListNode lastnode = prenode;? //定義循環(huán)用的對象
? ? ? ? ? ? while (l1 != null || l2 != null || val != 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? val = val + (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val); //計算兩數(shù)之和 并加上前一輪需要進(jìn)位的值
? ? ? ? ? ? ? ? lastnode.next = new ListNode(val % 10); //計算個位绘迁，將數(shù)據(jù)添加到循環(huán)鏈表中
? ? ? ? ? ? ? ? lastnode = lastnode.next;? //循環(huán)用的對象賦值為循環(huán)鏈表中的下一個對象
? ? ? ? ? ? ? ? val = val / 10;//計算十位并賦值
????????????????//l1 l2 指向自己在鏈表中對應(yīng)的下一個值
? ? ? ? ? ? ? ? l1 = l1 == null ? null : l1.next;
? ? ? ? ? ? ? ? l2 = l2 == null ? null : l2.next;
? ? ? ? ? ? }
? ? ? ? ? ? return prenode.next;
? ? ? ? }
? ? }
? ? class Test
? ? {
? ? ? ? static ListNode generateList(int[] vals)
? ? ? ? {
? ? ? ? ? ? ListNode res = null;
? ? ? ? ? ? ListNode last = null;
? ? ? ? ? ? foreach (var val in vals)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (res == null)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? res = new ListNode(val);
? ? ? ? ? ? ? ? ? ? last = res;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? last.next = new ListNode(val);
? ? ? ? ? ? ? ? ? ? last = last.next;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return res;
? ? ? ? }
? ? ? ? static void printList(ListNode l)
? ? ? ? {
? ? ? ? ? ? while (l != null)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Console.Write($"{l.val}, ");
? ? ? ? ? ? ? ? l = l.next;
? ? ? ? ? ? }
? ? ? ? ? ? Console.WriteLine("");
? ? ? ? }
? ? ? ? static void Main()
? ? ? ? {
? ? ? ? ? ? var l1 = generateList(new int[] { 2, 5, 8 });
? ? ? ? ? ? var l2 = generateList(new int[] { 3, 6, 9, 1 });
? ? ? ? ? ? printList(l1);
? ? ? ? ? ? printList(l2);
? ? ? ? ? ? Solution s = new Solution();
? ? ? ? ? ? var sum = s.AddTwoNumbers(l1, l2);
? ? ? ? ? ? printList(sum);
? ? ? ? }
? }
