2. Add Two Numbers

系统管理员 2023-02-16 00:50 84阅读 0赞

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

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

***思路分析***  
1：所给的俩个链表都是不为空的，且不为0开头  
2：所给俩个链表都是按照： 个位，十位，百位，由低到高的，因此可以直接对俩个链表进行从头部开始逐位的运算  
3：注意考虑到进位的问题，但由于是加法，所以进位最大也是1，每次运算时需要加上前一步的进位值  
4：需要考虑俩个链表长度不一的问题，即判空的情况  
5：注意最终结果链表的更新和最高位是否有进位情况

public class Solution { 
    
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            ListNode p1 = l1;
            ListNode p2 = l2;
              //构建一个初始值，用于后续链接，当前节点无实际存储值
            ListNode current = new ListNode(0);
            ListNode result = current;
            int carry = 0;
    
            while (p1 != null || p2 != null) { 
                //获取第一个链表的当前数字
                int a = (p1 != null) ? p1.val : 0;
                //获取第二个链表的当前数字
                int b = (p2 != null) ? p2.val : 0;
                //获取当前加法运算总数
                int sum = a + b + carry;
                //更新进位值carry
                carry = sum / 10;
                //链接结果链表
                current.next = new ListNode(sum % 10);
                //更新指针
                current = current.next;
                if (p1 != null) p1 = p1.next;
                if (p2 != null) p2 = p2.next;
    
            }
            //处理最高位的进位
            if (carry > 0) { 
                current.next = new ListNode(carry);
            }
            return result.next;
        }
    
        /** * (2 -> 4 -> 3) + (5 -> 6 -> 4) * 输出：7 -> 0 -> 8 * 原因：342 + 465 = 807 */
        public static void main(String[] args) { 
            ListNode p1 = new ListNode(2);
            ListNode p2 = new ListNode(4);
            ListNode p3 = new ListNode(3);
            ListNode p4 = new ListNode(5);
            ListNode p5 = new ListNode(6);
            ListNode p6 = new ListNode(4);
            p1.next = p2;
            p2.next = p3;
            p4.next = p5;
            p5.next = p6;
            ListNode listNode = new Solution().addTwoNumbers(p1, p4);
            while (listNode != null) { 
                System.out.println(listNode.val);
                listNode = listNode.next;
            }
    
        }
    }

***复杂度分析***  
时间复杂度：O（max（m，n）），m 和 n 代表 l1 和 l2 的长度。 空间复杂度：O（max（m，n）），m 和 n 代表 l1 和 l2 的长度。而其实新的 List 最大长度是 O（max（m，n））+ 1，这个1是因为使用了作为head节点，但该节点并没有存储实际有用的值

[20200606214039724.png]: https://img-blog.csdnimg.cn/20200606214039724.png