题目

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 -> 8
Explanation: 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<ListNode> addTwoNumbers(ListNode l1, ListNode l2,List<ListNode> 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<ListNode> list1=new ArrayList<>();
        List<ListNode> 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<ListNode> listNodesRes=new ArrayList<>();
        int minLength=Math.min(list1.size(),list2.size());
        for(int i=0;i<minLength;i++){
            addTwoNumbers(list1.get(i),list2.get(i),listNodesRes);
        }
        if (list1.size()-minLength>1){
            for(int i=minLength;i<list1.size();i++){
                listNodesRes.add(list1.get(i));
            }

        }
        if (list2.size()-minLength>=1){
            for(int i=minLength;i<list2.size();i++){
                listNodesRes.add(list2.get(i));
            }

        }
        listNodesRes.forEach(listNode -> {
            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);



    }
}

运行结果：