力扣算法Java热门面试题链表两数相加，力扣算法学习之路

忘是亡心i 2023-10-02 15:32 14阅读 0赞

力扣高频算法题的第二道，两数相加，两个链表上的数相加，题目如下

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_17_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_17_color_FFFFFF_t_70_g_se_x_16 1][]

**示例1的解释容易误解，他是把数字倒过来相加，用在示例3上是行不通的，结合示例1和示例3 的结果，合理的解释这样的：两个链表的首位相加，大于等于10则取余10作为首位的结果，然后链表后一位相加的时候，在原相加的结果再加上1，如果小于10，则后面相加的结果不加一，如果链表末面两位结果大于等于10，链表的长度需要加一，且末尾是1**

/**
     * @author qiankun.hu
     * @version 1.0.0
     * @createTime 2021年11月15日
     * @Description 两数相加 链表
     */
    public class TwoNumber {
    
        public static void main(String[] args) {
            ListNode node5 = new ListNode(9,null);
            ListNode node4 = new ListNode(9,node5);
            ListNode node3 = new ListNode(9,node4);
    
            ListNode node2 = new ListNode(9,null);
            ListNode node1 = new ListNode(9,node2);
    
            ListNode node = addTwoNumbers(node3,node1);
    
        }
    
        /**
         * 两数之和 链表形式
         * @param l1
         * @param l2
         * @return
         */
        public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            //首位末尾0，取结果的时候不要首位就行了
            ListNode newNode = new ListNode(0);
            ListNode curNode = newNode;
            //进位 即两位数相加结果大于等于10则往后传递1，后面两数相加的结果再加上1
            int cur = 0;
            while(l1!=null||l2!=null){
                //为空则默认0
                int a = l1 == null ? 0 : l1.val;
                int b = l2 == null ? 0 : l2.val;
    
                int sum = a+b+cur;
                //大于10进位 
                cur = sum / 10;
                // 取余 
                sum = sum % 10;
    
                curNode.next = new ListNode(sum);
                curNode = curNode.next;
                //分别后移，下一位的计算
                if (l1 != null) l1 = l1.next;
                if (l2 != null) l2 = l2.next;
            }
            //如果最后面末尾相加的结果大于等于10（即进位==1）,则链表的下一位为1
            if (cur==1){
                curNode.next = new ListNode(1);
            }
            return newNode.next;
        }
    
    
    
        static class ListNode {
            int val;
            ListNode next;
            ListNode() {}
            ListNode(int val) { this.val = val; }
            ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    
        }
    
    
    }

解题方法来自力扣题解精选

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4178b0616ecd40f6987610bc678c8d9a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_17_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b258a324210247cdbb014dfcf6cd31fa.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k,size_17,color_FFFFFF,t_70,g_se,x_16