02. 两数相加(链表)

题目

分析：

题中给的两个链表里的数是反着排的。
迭代求和，直到两个链表都走完了。
若其中一个链表走完了而另一个还没有，则：
3.1 返回链表的当前节点值就为还未走完的链表的当前值
3.2 也可以为0加上此值
按照加法运算法则相加
我们判断链表是否走完是要判断当前链表的 next 是否为 null , 故我们可以使用do{}while();语句迭代
5.1 后改为l1 = l1.next; l2 = l2.next;使用while语句
返回值是结果链表的头结点 , 且此链表是单向链表 , 所以我们还需一个当前节点 , 以此对结果链表进行操作

正确代码：

https://www.cnblogs.com/grandyang/p/4129891.html

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int d1 = l1 == null ? 0 : l1.val;
            int d2 = l2 == null ? 0 : l2.val;
            int sum = d1 + d2 + carry;
            carry = sum >= 10 ? 1 : 0;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry == 1) cur.next = new ListNode(1);
        return dummy.next;
    }
}

错误代码：

代码1.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode reListNode;        //返回节点 , 即结果链表
        while((l1 == null) && (l2 == null)){
            short l1Val = (l1 == null)? 0 : l1.val;
            short l2Val = (l2 == null)? 0 : l2.val;       //针对其中一个链表已经结束的情况

            ListNode nowListNode = new ListNode();
            reListNode = nowListNode;       //保存头结点 , 错误
            nowListNode = nowListNode.next; 
            l1 = (l1 == null)? null : l1.next;
            l2 = (l1 == null)? null : l1.next;        //更新当前节点

        }
        return reListNode;
    }
}

//保存头结点 会一起迭代 , 故未起到作用
解决方法 :

创建变量表示头结点是否保存(会占用不少的时间, 和一小块儿空间)
在循环外面写
可以定义辅助接点解决(最好)

代码 2.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode nowListNode;       //当前节点
        ListNode reListNode;        //返回节点 , 即结果链表
        int l1Val;
        int l2Val;        //当前的val
        int result;       //当前结果
        int carry;        //进位:1 ; 不进:0
        int defhead = 0;  //是否保存头结点 , 可以用bool节省空间 , 且表意更明确
        while((l1 == null) && (l2 == null)){
            l1Val = (l1 == null)? 0 : l1.val;
            l2Val = (l2 == null)? 0 : l2.val;       //针对其中一个链表已经结束的情况
            if((result = (l1Val+l2Val)) > 9){
                carry = 1;
                result = result + carry - 10;
            }else{
                carry = 0;
                result = result + carry;        //加法法则
            }
            nowListNode = new ListNode(result);
            if(0 == defhead){
                reListNode = nowListNode;       //保存头结点
                defhead = 1;
            }
            nowListNode = nowListNode.next; 
            l1 = (l1 == null)? null : l1.next;
            l2 = (l1 == null)? null : l1.next;        //更新当前节点

        }
        return reListNode;
    }
}

报错 : Line 38: error: variable reListNode might not have been initialized
将reListNode 初始化为null后成功编译 , 但无结果输出

解决方式 :

定义一个辅助节点 , 用以解决头结点的保存
while判断有错误 , while((l1 == null) && (l2 == null)) , 这句的意思是两个节点都为空才执行里面的内容
若最后两数和结果的位数大于大于这两个数中的任意一个 , 即最高位相加后依旧进位 , 需再创建一个节点 , 并将其值设为 1

代码 3.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode secondaryNode = new ListNode(-1);        //辅助节点
        ListNode nowListNode = secondaryNode;       //当前节点 

        int result;       //当前结果
        int carry = 0;        //进位:1 ; 不进:0
        while((l1 != null) || (l2 != null)){
            int l1Val = (l1 == null)? 0 : l1.val;
            int l2Val = (l2 == null)? 0 : l2.val;       //针对其中一个链表已经结束的情况
            if((result = (l1Val+l2Val)) > 9){
                carry = 1;
                result = result + carry - 10;
            }else{
                carry = 0;
                result = result + carry;        //加法法则
            }
            nowListNode.next = new ListNode(result);    //保存结果
            l1 = (l1 == null)? null : l1.next;
            l2 = (l1 == null)? null : l1.next;        //更新当前节点
        }
        if(1 == carry){
            nowListNode.next = new ListNode(1);
        }
        return secondaryNode.next;
    }
}

问题 1 :

当前节点没有往后面走
解决 :

nowListNode.next = new ListNode(result); // 保存结果
nowListNode = nowListNode.next;

问题 2 :

l2更新时使用了l1的值
解决 :

问题 3 :

判断 l2 当前节点是否为空时使用了l1进行判断
解决 :

问题 4 :

先判断结果是否>9后再加上进的一位1 , 这样若是当前result为9 , 则最终result为10
解决 :
最后在进行是否>9的判断 , 必须确保每一位都在0~9间

/*
 * @lc app=leetcode.cn id=2 lang=java
 *
 * [2] 两数相加
 */

// @lc code=start

//Definition for singly-linked list.
// class ListNode {
//     int val;
//     ListNode next;

//     ListNode(int x) {
//         val = x;
//     }
// }

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode secondaryNode = new ListNode(-1); // 辅助节点
        ListNode nowListNode = secondaryNode; // 当前节点
        int result = 0; // 当前结果
        int carry = 0; // 进位:1 ; 不进:0
        while ((l1 != null) || (l2 != null)) {
            int l1Val = (l1 == null) ? 0 : l1.val;
            int l2Val = (l2 == null) ? 0 : l2.val; // 针对其中一个链表已经结束的情况
            result = l1Val + l2Val + carry;
            carry = (result > 9) ? 1 : 0;
            nowListNode.next = new ListNode(result % 10); // 保存结果
            nowListNode = nowListNode.next;
            l1 = (l1 == null) ? null : l1.next;
            l2 = (l2 == null) ? null : l2.next; // 更新当前节点
        }
        if (1 == carry) {
            nowListNode.next = new ListNode(1);
        }
        return secondaryNode.next;
    }
}
// @lc code=end