本文共 4510 字，大约阅读时间需要 15 分钟。

题目

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:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8Explanation: 342 + 465 = 807.

刚开始没有理解正确，解释一下，比如数字在链表中是倒序存储的，上面的例子中，342链表结构是2-4-3，465链表结构是5-6-4。342和465相加结果为807，对应的链表结构是7-0-8

我的尝试

这个题目时间复杂度比较容易处理，是O（2n）。但是需要注意的情况比较多，分别是：

1. 长度不同情况

2. 发生进位的情况，一种是普通进位，一种是进位在最高位，这个时候需要添加node

package com.puhui.flowplatform;import java.util.ArrayList;import java.util.List;/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public static  List
   
     addTwoNumbers(ListNode l1, ListNode l2,List
    
      listRes) {        //最高位进位返回两个node        ListNode listNodeCreated=new ListNode(0);        int sum=l1.getVal()+l2.getVal();        if(sum%10==0){            //发生进位，此位比为0            listNodeCreated.setVal(0);            listRes.add(listNodeCreated);            ListNode nextNode=l1.getNext();            if(nextNode==null){                //最高位进位，增加新的节点                ListNode listNodeNew=new ListNode(0);                listNodeNew.setVal(1);                listRes.add(listNodeNew);            }            else{                //非最高位正常进位,加1到下一位                nextNode.setVal(nextNode.getVal()+1);            }        }        //不发生进位        else{            listNodeCreated.setVal(sum);            listRes.add(listNodeCreated);        }        return listRes;    }    public static void  main(String[] args){        List
     
       list1=new ArrayList<>();        List
      
        list2=new ArrayList<>();        //list1        ListNode listNode1=new ListNode(1);        ListNode listNode2=new ListNode(5);        ListNode listNode3=new ListNode(3);        list1.add(listNode1);        list1.add(listNode2);        list1.add(listNode3);        //list2        ListNode listNode4=new ListNode(4);        ListNode listNode5=new ListNode(5);        ListNode listNode6=new ListNode(6);        listNode1.setNext(listNode2);        listNode2.setNext(listNode3);        listNode4.setNext(listNode5);        listNode5.setNext(listNode6);        list2.add(listNode4);        list2.add(listNode5);        list2.add(listNode6);        List
       
         listNodesRes=new ArrayList<>();        int minLength=Math.min(list1.size(),list2.size());        for(int i=0;i
        
         1){ for(int i=minLength;i
         
          =1){ for(int i=minLength;i
          
            { System.out.println(listNode.getVal()); }); }}
          
         
        
       
      
     
    
   

优化方法

有人用递归实现，也可以用以下方法，思路基本相同，代码简洁很多，利用两个指针p和q，从链表头指针开始，计算当前p和q对应元素和，对10求余数和求模，计算出节点数值以及进位数值。一直循环到p和q都为空。在循环中，取出当前值需要判断p和q是否为空，为空则为0，因为两个链表长度不同情况下，val为空。

此时如果p和q都为空，那么就是全部处理完毕，判断addnumber也就是进位数数否有值，如果有，创建新的节点，容易忽略最高位进阶对情况。

package com.puhui.flowplatform;/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    /**     * 两个链表的头指针开始遍历     * @param l1     * @param l2     * @return     */    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode resultHead=new ListNode(0);        ListNode p=l1,q=l2,current=resultHead;        int addNumber=0;        while (p!=null||q!=null){            //防止长度不一样，一个指针为空，直接取0            int sum=((p==null?0:p.getVal())+(q==null?0:q.getVal())+addNumber);            int number=sum%10;            addNumber=sum/10;            ListNode node=new ListNode(number);            current.next=node;            current=current.next;            if (p!=null){                p=p.next;            }            if (q!=null){                q=q.next;            }        }        //都到达链表尾部        if(addNumber!=0)        {            current.next=new ListNode(1);        }        return resultHead.next;    }    public static void  main(String[] args){        ListNode listNode1=new ListNode(1);        ListNode listNode2=new ListNode(5);        ListNode listNode3=new ListNode(3);        ListNode listNode4=new ListNode(4);        ListNode listNode5=new ListNode(5);        ListNode listNode6=new ListNode(6);        //不需要list，建立链表关系        listNode1.setNext(listNode2);        listNode2.setNext(listNode3);        listNode4.setNext(listNode5);        listNode5.setNext(listNode6);        addTwoNumbers(listNode1,listNode4);    }}

运行结果：

转载地址：https://kerry.blog.csdn.net/article/details/83411031 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！