【剑指Offer】两数相加II

给定两个非空链表l1和l2来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

/** * 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) { // 思路：用两个栈存储两个链表的所有节点，存储完毕后开始出栈进行相加 // 定义两个栈s1和s2存储所有的节点 Stack<int> s1 = new(); Stack<int> s2 = new(); ListNode l1Clone = l1; ListNode l2Clone = l2; PushToStack(l1Clone, s1); PushToStack(l2Clone, s2); // 定义一个bool表示下个数是否需要进一 bool addOne = false; // 定义一个空节点表示结果的头节点resultNode ListNode resultNode = null; // 找出栈元素更多的那个栈的数量 int n = s1.Count >= s2.Count ? s1.Count: s2.Count; // 进行一个while循环，循环条件为Count较大的那个栈栈顶还有元素 while(n > 0 || addOne) { // 计算节点的值 int _val = 0; if(s1.TryPop(out int num1)) _val += num1; if(s2.TryPop(out int num2)) _val += num2; // 判断是否需要进一 if(addOne) { _val ++; addOne = false; } // 判断是否大于10，若大于10则减去10且下次要进一 if(_val >= 10) { _val -= 10; addOne = true; } // 每次循环创建一个新的节点，该节点的下一个节点为resultNode ListNode tmpNode = new ListNode(val: _val, next: resultNode); // 让resultNode指向该新节点 resultNode = tmpNode; // n -- n --; } // 返回resultNode return resultNode; } private void PushToStack(ListNode node, Stack<int> stack) { while(node != null) { stack.Push(node.val); node = node.next; } } }