問題描述
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
問題解析
非負(fù)鏈表，以反向排列來表示數(shù)值，（2 -> 4 -> 3）表示342卦停，（5 -> 6 -> 4)表示465宵荒，342與465相加的結(jié)果為807羽氮，所以最終要求的結(jié)果就是(7 -> 0 -> 8).
由于鏈表是反向矿筝，因此數(shù)值運(yùn)算從個(gè)位開始也就是從鏈表第一位開始相加吆视，如果大于10則進(jìn)位希俩，然后進(jìn)行第二位的相加吊宋，以此類推直到最后一位。
要點(diǎn)：
- 要注意的就是一些特殊情況颜武，比如說兩個(gè)鏈表不等長的情況璃搜，還有就是最后一位的高位進(jìn)位要考慮。
- 對于鏈表的處理也是個(gè)重點(diǎn)鳞上，用鏈表的尾插法來處理是個(gè)人認(rèn)為比較好的方式这吻，但是下面給出的示例代碼并沒有有尾插法來做，那只是個(gè)人的偷懶（PS:好吧說實(shí)話篙议，那時(shí)寫的時(shí)候忘了尾插法是怎么實(shí)現(xiàn)的了唾糯，后面一定找個(gè)時(shí)間用尾插法重新實(shí)現(xiàn)一遍）怠硼。
示例代碼
<pre>
'' public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
'' //進(jìn)位標(biāo)識
'' boolean carryFlag = false;
'' //補(bǔ)高位標(biāo)識
'' boolean highFlag = false;
'' List<ListNode> listNodes = new ArrayList<>();
'' ListNode p1 = l1;
'' ListNode p2 = l2;
'' while (null != p1 || null != p2) {
'' int value1 = 0;
'' int value2 = 0;
'' if (null != p1) {
'' value1 = p1.val;
'' }
'' if (null != p2) {
'' value2 = p2.val;
'' }
'' int value = value1 + value2;
'' if (carryFlag) {
'' value = value + 1;
'' //進(jìn)位標(biāo)識清空
'' carryFlag = false;
'' }
''
'' //進(jìn)位處理
'' if (value > 9) {
'' value = value % 10;
'' carryFlag = true;
'' //高位為空時(shí)，新增高位處理
'' if (((null != p1 && null == p1.next) && (null == p2 || null == p2.next)) || ((null != p2 && null == p2.next) && (null == p1))) {
'' highFlag = true;
'' }
'' }
'' listNodes.add(new ListNode(value));
''
'' //鏈表后移處理
'' if (null != p1 && null != p1.next) {
'' p1 = p1.next;
'' } else {
'' p1 = null;
'' }
'' if (null != p2 && null != p2.next) {
'' p2 = p2.next;
'' } else {
'' p2 = null;
'' }
'' }
'' //最后新增高位
'' if(highFlag) {
'' listNodes.add(new ListNode(1));
'' }
''
'' for (int i = 0; i < listNodes.size() - 1; i++) {
'' listNodes.get(i).next = listNodes.get(i + 1);
'' }
''
'' return listNodes.get(0);
'' }
</pre>
