力扣第2题-- 两数相加

本是古典何须时尚 2022-12-18 13:56 136阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70_pic_center]

起初对于这题我有点轻视，简单的想先把这个链表所表达的值先算出来，例如2->4->3就是342  
没有想过这个链表所表达的值可能超过基本类型int、long。然后将转换后的两个数字相加，得到这个值807，然后想利用StringBuilder的reverse方法得到708，但是结果报了数值越界异常。

### 因此这一题的坑：`没有提示链表所表示的值可能超过基本类型` ###

--------------------

### 转换思路的解法 ###

既然链表是倒叙的，那么也就是说第一个节点是这个数字的最小值也可以称为个位数  
第二个节点则都是十位数…  
那么按照顺序将每一个节点相加得到一个新的链表。只是这个链表的每一个节点可能超过9。也就是说需要进一  
我们发现9+9是18，取8进1，而高一位即使得到的也是9+9=18，那么18+1=19无论如何都不可能得到20，就是说每一个节点最多进1  
那么剩下对每一个节点操作，如果节点`val>=10`，下一个节点的`val+=1`，同时自身节点的值需要`val%=10`

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
    class Solution { 
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            ListNode l3 = l1, last = null;
            int c = 0, t1, t2;
            while (l1 != null || l2 != null) { 
                if (l1 == null) { 
                    t1 = 0;
                } else { 
                    t1 = l1.val;
                }
                if (l2 == null) { 
                    t2 = 0;
                } else { 
                    t2 = l2.val;
                }
                ListNode tmp = new ListNode(t1 + t2);
                if (c == 0) { 
                    l3 = tmp;
                    last = tmp;
                    c++;
                } else { 
                    last.next = tmp;
                    last = last.next;
                }
                if (l1 != null)
                    l1 = l1.next;
                if (l2 != null)
                    l2 = l2.next;
            }
            l1 = l3;
            while (l1 != null) { 
                if (l1.val >= 10) { 
                    l1.val %= 10;
                    if (l1.next == null) { // 特殊情况，例如124 456，高位4+6 >=10需要加一个节点
                        l1.next = new ListNode(1);
                        break;
                    }
                    l1.next.val += 1;
                }
                l1 = l1.next;
            }
            return l3;
        }
    
    }

没想到效率还不错，击败了99.92%的用户。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/04de0b880e4e431fbb5c7f76d0fbf3ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODEzMjA4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/56dff3eafad448d89bad202e569a219a.png