LeetCode Problems Solutions

question description:问题描述

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开发，除非是0数字本身。

简单理解：就是将两个链表对应节点的数字相加，大于10的取其余数并向后进一位，返回一个新的链表。(此处的链表也就是下面的ListNode,其实可以理解为一个带有自身属性的类)
Example:

/**
 * Definition for singly-linked list. //定义一个单链表
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; } //构造方法
 * }
 */

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Thinking

有三点需要我们搞清楚：
a.每个节点的val值就是 去 给定的两个链表的对应节点 的val值 相加 取模(%)得到
b.每个节点的val值还受上一个节点的val值相加 除以10 取商 的影响，所以在a中，两个链表的对应节点 的val值 相加 后，还需在上一个节点的 商值。
c.返回的链表每个节点的数字(val值)是由上一个节点的next值决定，也就是链表的尾节点
所以，我们可以先确定最终链表的第一个节点，然后不断的去设置该链表的next值去确定后面的节点。

solution with java - Java解决方案

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

//先确定第一个节点
        ListNode result = new ListNode((l1.val + l2.val) % 10);
//记录第一个节点对下一个节点的影响，是否进一位
        int count = (l1.val + l2.val) / 10;
        int index = 0; // 记录设置到了第几个节点

        ListNode node1 = l1.next;
        ListNode node2 = l2.next;

//两个链表的长度可能不一样，最终next的值同时为空时停止循环
        while (node1 != null || node2 != null){

            index += 1;
           

            int arg1 = (node1 == null) ? 0 : node1.val;
            int arg2 = (node2 == null) ? 0 : node2.val;

            int val = (arg1 + arg2) % 10;
            int nextVal = (count + arg1 + arg2) / 10;

            ListNode temp = new ListNode((count + val) % 10);

            //把result的最后一个next赋值为temp
            result = method(index-1,result,temp);


//更新循环条件
            count = nextVal;
            if (node1 != null){
                node1 = node1.next;
            }
            
            if (node2 != null){
                node2 = node2.next;
            }
            
        }
       
//当两个链表长度一样，且最后的节点数字相加大于10，此时，新的链表长度会多一个节点，也就是count = 1，这里直接使用 count > 0也没有问题。
       if (count > 0){
           
           ListNode temp = new ListNode(count);
           
           result = method(index,result,temp);
       }

        return result;


    }
    
    // 递归解决修改 链表指定位置元素的next值

/*
index:修改链表的第几个节点的next值，从0开始
result:要修改的目标链表
value:修改的值
*/

    private ListNode method(int index, ListNode result, ListNode value){

        if (index > 0){

            index -= 1;

            result.next = method(index, result.next,value);

        }else{
            result.next = value;
            return result;
        }

        return result;

    }

solution with swift - swift解决方案

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        //先确定第一个节点
        var result = ListNode(((l1?.val)! + (l2?.val)!) % 10);
        //记录第一个节点对下一个节点的影响，是否进一位
        var count = ((l1?.val)! + (l2?.val)!) / 10;
        var index = 0;// 记录设置到了第几个节点
        
        var node1 = l1?.next;
        var node2 = l2?.next;
        //两个链表的长度可能不一样，最终next的值同时为空时停止循环
        while (node1 != nil || node2 != nil){
            
            index += 1;
            
            
            let arg1 = (node1 == nil) ? 0 : node1?.val;
            let arg2 = (node2 == nil) ? 0 : node2?.val;
            
            let val = (arg1! + arg2!) % 10;
            let nextVal = (count + arg1! + arg2!) / 10;
            
            let temp = ListNode((count + val) % 10);
            
            //把result的最后一个next赋值为temp
            result = method(index: index-1,result: result,value: temp);
            

//更新循环条件
            count = nextVal;
            if (node1 != nil){
                node1 = node1?.next;
            }
            if (node2 != nil){
                
                node2 = node2?.next;
            }
  
        }
        
        if (count > 0){
            
            let temp = ListNode(count);
            
            result = method(index: index,result: result,value: temp);
        }

        return result;
    
    }
    

    // 递归解决修改 链表指定位置元素的next值
/*
index:修改链表的第几个节点的next值，从0开始
result:要修改的目标链表
value:修改的值
*/
    func method(index:Int, result : ListNode, value : ListNode)->ListNode{
    
        var i = index
        
        if (i > 0){
            
            i -= 1;
            
            result.next = method(index: i, result: result.next!,value: value);
            
        }else{
            result.next = value;
            return result;
        }
        
        return result;
        
    }