[数据结构与算法][Leetcode篇]链表中的两数相加

题目描述：

剑指offerII 025

💌算法思路：

相信许多人拿到这个题的时候，会想这不就so easy嘛，直接让两数每个数字位上的元素相加不就完事了吗？
不不不，我们要注意的是题目中的描述，他说数字的最高位在单链表的头节点，而最低位在单链表的尾节点，学习过链表基础的同学，肯定会想单链表只能从头节点遍历到尾节点，我们在数字相加的时候，要从低位加起，所以要从链表的尾节点遍历到链表的头节点，所以说求解此题第一步，翻转两个要进行相加的链表。到了第二步，我们在数字相加的时候要注意满10进1，千万不要忘记了，类似的当相加之后，是999 + 9 = 1018时，还要在申请一个空间来存放进1的那一位。注意相加之后的链表，是从个位遍历到高位的，也就是说链表还要进行翻转，这样头节点才能指向最高位数字，从而读出相加之后的数字。

看图说话：

💯代码：

 
 public Node addList() {
    //第一步翻转链表
        headA = reverseList(headA);
        headB = reverseList(headB);
        //链表相加
        Node node = addNode(headA,headB);
        return reverseList(node);
    }

    public Node addNode(Node headA,Node headB){
        Node dummy = new Node(-1); //建立虚拟节点
        Node cur = dummy;
        int sum = 0;
        int carry = 0;
        while(headA != null || headB != null){
            sum = (headA == null ? 0 : headA.val) + (headB == null ? 0 : headB.val) + carry;
            carry = sum >= 10 ? 1 : 0;//进一
            //如果两个数相加大于10，那么就在这一位保留sum - 10
            sum = sum >=10 ? sum - 10 : sum;
            //新建节点，把计算后的值，放到新建节点中
            Node newNode = new Node(sum);
            cur.next = newNode;
            cur = cur.next;
            //遍历两个相加链表
            headA = headA == null ? null : headA.next;
            headB = headB == null ? null : headB.next;
        }
        if(carry > 0){
            cur.next = new Node(carry);
        }
        return dummy.next;
    }
    //翻转链表
    public Node reverseList(Node node){
        Node newhead = null;
        Node cur = node;
        while(cur!=null){
            Node curNext = cur.next;
            cur.next = newhead;
            newhead = cur;
            cur = curNext;
        }
        return newhead;
    }
   //链表打印
    public void print(Node node){
        Node cur = node;
        while(cur!=null){
            System.out.print(cur.val + " ");
         cur = cur.next;
        }
    }