day3 02 两数相加

单链表算法题

题目：两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和您可以假设除了数字 0 之外，这两个数都不会以 0 开头。。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：

这道题涉及单链表数据结构，两个链表的从头结点开始加和，结果值每次存贮在新链表的尾节点，考虑进位问题。最后把新链表从头节点开始输出。涉及到的算法就是单链表如何从尾部 push 节点。

1.首先需要创建一个新的链表用来返回结果（res）

2.需要一个指针指向链表的最后一个节点，以便每次从尾部添加新的节点（resTemp）

ListNode resTemp = res;//先把指针指向新建的链表 res，此时 resTemp 指向新链表

3.节点相加的问题

• 当链表节点相加，可能会存在进位，比如 6+7 = 13，新节点的值应该是 13 % 10 = 3，需要进位值是 13 / 10 = 1。因此需要一个变量来存储进位的值（nextSum）
• 链表的第一个节点相加是不需要考虑是否添加进位值，因此设置一个flag变量，控制节点是否是第一个。
• 对于新节点来说，节点的data值是 p % 10;, 上一个节点指针指向新节点

resTemp.next = new ListNode(p % 10);// 让前一个节点指向一个新的节点，这个节点的data是加和之后的结果

resTemp = resTemp.next;//让resTemp 现在指指向新的节点 这就是从链表尾部添加元素的语法

4.创建单链表并添加节点问题

可以参考上图

• 首先新建一个空的链表 ListNode res = new ListNode();
• 新建一个辅助指针，指向链表的节点 ListNode resTemp = res; ，让这个辅助指针和链表指向同一个地址
• 我们需要添加节点的时候，让辅助指针指向一个新的节点，此时链表也就指向了这个新节点（链表添加节点成功）resTemp.next = new ListNode(p % 10 )。
• 让辅助指针 和 新添加的节点 指向同一个地址，resTemp = resTemp.next; 借助辅助指针陆续添加节点。每次先让辅助指针和当前节点指向一样，然后让辅助指针指向新节点，然后又让辅助指针和新节点的指向一样。。。。。
• 当前节点处于倒数第二个节点时，辅助指针指向最后一个节点，不需要再更改指向。

5.考虑两个链表的节点个数可能不相等，可能 a 链表已经没有节点了，b 链表还有数组，此时下一个节点的值是 b 链表的值和进位值的叠加。

6.最后当两个链表都为 null ，但是存在不为 0 的进位值，需要再添加一个节点，此时只需要让 上一个节点指向一个data 是进位值的新节点即可。

/**
 * 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 res = new ListNode();//新建一个链表，返回计算之后的结果
        ListNode resTemp = res; //这是一个辅助指针，指向最后一个节点
        int nextSum = 0; //进位值
        int flag = 0 ;//链表节点，0表示是链表的第一个节点
        while(l1 != null && l2 != null){
            int p ;
            if(flag == 0){//第一个节点不需要考虑是否进位
                p = l1.val + l2.val;
                res.val = p % 10;
                nextSum = p /10;
                flag ++;
            }else{
                p = l1.val + l2.val + nextSum;
                resTemp.next = new ListNode(p % 10);//上一个指针指向新节点
                resTemp = resTemp.next;
                nextSum = p / 10;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        //l1还有剩余节点
        while (l1 != null){
            int p = l1.val + nextSum;
            resTemp.next = new ListNode(p % 10) ;
            resTemp = resTemp.next;
            nextSum = p / 10;
            l1 = l1.next; 
        }
        //l2还有剩余节点
        while(l2 != null) {
            int p = l2.val + nextSum;
            resTemp.next = new ListNode(p % 10) ;
            resTemp = resTemp.next;
            nextSum = p / 10;
            l2 = l2.next; 
        }
        // nextSum 不为0
        if(nextSum != 0)
        resTemp.next = new ListNode(nextSum);
        return res;
    }
}

赏

谢谢你请我吃糖果