leetcode02

链表相加

​ 题目： 给定两个非空链表，存放的数据都是非负整数，并且都是按照逆序的方式进行存储，要求把这两个数字相加，并返回同样的链表。

​ LeetCode的题目描述都令人头大。直接写个例子。

​ 假设有两个链表：

​ 链表1： 2 —->>>> 4 —->>>> 3

​ 链表2： 5 —->>>> 6 —->>>> 4

由于是逆序的，所以数字是 342和465

相加得到 342+465=807

所以返回的链表是 ： 7 —->>>> 0 —->>>> 8

---

​ 两个个位数相加，如果大于10 ，需要进1。。 所以，设置一个溢出位，如果遍历到的当前节点相加大于10， 则设置溢出位的值为1，在下一个节点相加之前，加上这个值。在计算这个溢出位时，可以直接通过sum/10 来计算， 因为，如果sum = num1 + num2 + carry(溢出位) 大于10， 则需要进1， 否则为 0.

---

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //创建一个新的头结点
        ListNode l3 = new ListNode();
        //创建指针
        ListNode cursor = l3;
        //初始化溢出位的值
        int carry = 0;
        //遍历两个链表
        while (l1 != null || l2 != null || carry != 0) {
            //carry ！= 0 是为了防止最后一位数字大于10，需要进1
            int num1 = ( l1 == null ) ? 0 : l1.val;
            int num2 = ( l2 == null ) ? 0 : l2.val;
            //计算和
            int sum = num1 + num2 + carry;
            //得到溢出位的值
            carry = sum /10;
            //创建一个新的节点挂到l3的后面，sum % 10 有可能得到的sum是大于10的
            ListNode newNode = new ListNode(sum % 10);
            cursor.next = newNode;
            //指针后移
            cursor = cursor.next;
            
            //l1,l2后移
            if (l1.next != null) l1 = l1.next;
            if (l2.next != null) l2 = l2.next;
        }
        
        //将结果返回
        return l3.next;
    }
}

​ 验证一下,手动创建两个链表

public static void main(String[] args) {
        //创建l1
		ListNode l1 = new ListNode(2);
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(3);
        l1.next = listNode1;
        listNode1.next = listNode2;

        //创建l2
        ListNode l2 = new ListNode(5);
        ListNode listNode4 = new ListNode(6);
        ListNode listNode5 = new ListNode(4);
        l2.next = listNode4;
        listNode4.next = listNode5;

        ListNode l3 = addNumbers(l1, l2);
        ListNode cursor = l3;
        while (cursor != null){
            System.out.println(cursor.val);
            cursor = cursor.next;
        }
}

输出结果如下

输出结果：  7\n 0\n 8