Add Two Numbers

题目

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.

问题描述：
给定两个非空的非负数链表。每个节点包含一个数字，按照相反的顺序获取并转化为数字求和
可以假定除了个位位其他位不为0

Example

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

题目分析

/**
    简单翻译 ：
        给定两个非空的非负数的数字链表， 将其转数字相加后，将其相加和专为反向链表返回 
        input: 2  ----> 4---->3  + 5--->6---->4  
        运算： 342 + 465 = 807
        output: 7---->0----->8


问题重点：
    1. 两个链表 
    2. 非空非负整数的 
    3. 每个节点包含一个数字
    4. 相反的顺序获取

问题疑点： 
    1. 两个链表的位数相同吗 ，不同该怎么处理，高位补0吗？ 


解题思路：
    1. 将链表反向遍历转为字符串 
    2. 将字符串转为int 类型 
    3. sum int 类型 
    4. 反向获取int 类型的值转链表 
 */

题解

/**
    version 1
 */

class Solution_v1{
    private ListNode first;

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int lint1 =  listToInt(l1);
        int lint2 = listToInt(l2);
        return first;
    }

    private  int listToInt(ListNode l ){
        String str = "";
        while(l.next != null){
            str += String(l.next.data);
        }
        // string to int
    }

    private ListNode intToList(int sum){
        ListNode list = null;
        while(sum > 0){
            i = sum %10;
            ListNode node = new ListNode(i);
            node.pre = first;
            first.next = node;
            first = node;
            sum = sum / 10;
        }
    }

    class ListNode {
        ListNode next;
        ListNode pre;
        int data;
    } 
}   

/**
    总结：
        通过以上方式结题的时间复杂度 可能为 O(1) 不过可能会有变化 

        以上方式虽然可以解决问题，不过会需要其他的辅助行为
 */

/*-------------------------------------------------------*/
/**
    version 2
 */
 /**
    解题思路： 
        因为针对问题的分析是链表反过来用每位相加的方式，如果大于0 那么久进1 
        用其结果再次组织为一个链表  

        0. 一个临时变量，一个新的链表
        1. 反向遍历链表 
        2. 将链表的反向对应位置数字相加 
        3. 判断 临时变量 m 是否 > 0 
        4. 判断数字和其是否大于10 ，如果不大于10 
        5. 如果 3 成立 ， 在 4 基础上加 1 ，并至 临时变量 m = 0;
        6. 如果5 成立， 那么临时变量 m  = 1 ; 并以 5 个位创建节点
        7.  


  */
public Solution_v2{
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int m = 0;
        ListNode dum = new ListNode(0);



    }

    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }
}



/**
    算法总结： 

 */


/** 
 * 
 * 算法测试
 * 
 */

class Test {
    public static void main(String[] args) {
        System.out.println("测试结果"); 
        String str = "abacdefgeabcdef";


    }
}