445. 两数相加 II

港控/mmm° 2023-02-20 13:52 12阅读 0赞

# 题目来源 #

[445. 两数相加 II][445. _ II]

# 题目描述 #

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

# 题目解析 #

## 反转链表 ##

[2. 两数相加][2.] 的扩展

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        // 交换节点
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            l1 = reverseList(l1);
            l2 = reverseList(l2);
    
            ListNode dummy = new ListNode(-1);
            ListNode l = dummy;
            int c = 0;
            while (l1 != null || l2 != null){
        
                int a = l1 != null ? l1.val : 0;
                int b = l2 != null ? l2.val : 0;
                l.next = new ListNode( (a + b + c) % 10);
                c = (a + b + c)/10;
    
                l1 = l1 != null ? l1.next: null;
                l2 = l2 != null ? l2.next: null;
                l = l.next;
            }
    
            if(c != 0){
         // 易错点
                l.next = new ListNode(c);
            }
    
            return reverseList(dummy.next); // 易错点
        }
    
        public ListNode reverseList(ListNode listNode){
        
            ListNode pre = null, cur = listNode;
    
            while (cur != null){
        
                ListNode t = cur.next;
                cur.next = pre;
                pre = cur;
                cur = t;
            }
    
            return pre;
        }
    }

![在这里插入图片描述][20200627204406243.png]  
优化：插入新链表时可以采用头插法，这样就不需要反转链表了

## 使用栈 ##

> 利用栈后入先出的特性逆序访问链表

使用两个栈，遍历两个链表，将所有数字分别压入两个栈。

当两个栈有一个不为空时进入循环：【注意进位】

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        // 交换节点
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            Stack<Integer> stack1 = new Stack<>();
            Stack<Integer> stack2 = new Stack<>();
    
            while (l1 != null){
        
                stack1.push(l1.val);
                l1 = l1.next;
            }
    
            while (l2 != null){
        
                stack2.push(l2.val);
                l2 = l2.next;
            }
    
            ListNode dummp = new ListNode(-1);
            int c = 0;
            while (!stack1.empty() || ! stack2.empty() || c > 0) {
        
                int sum = c;
                sum  += stack1.empty() ? 0 : stack1.pop();
                sum  += stack2.empty() ? 0 : stack2.pop();
    
                ListNode l = new ListNode(sum % 10);
                l.next = dummp.next;
                dummp.next = l;
    
               c = sum / 10;
            }
    
            
            return dummp.next;
        }
    
    
    }

![在这里插入图片描述][2020062721051579.png]

## 递归 ##

[待研究][Link 1]

[445. _ II]: https://leetcode-cn.com/problems/add-two-numbers-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020062721072722.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[2.]: https://blog.csdn.net/zhizhengguan/article/details/106135859
[20200627204406243.png]: https://img-blog.csdnimg.cn/20200627204406243.png
[2020062721051579.png]: https://img-blog.csdnimg.cn/2020062721051579.png
[Link 1]: https://www.cnblogs.com/grandyang/p/6216480.html