题解 | #链表相加(二)#

思路

类似大数相加，逐位相加带上进位即可。

• reverse两个链表，方便后面从低位往高位逐位相加；
• 创建新结点，找个哨兵结点记录这个结点，初始化一个变量用来记录进位；
• 反转后的两个链表都不为空时，记录两个结点值以及进位值的和记为sum，新结点值为sum%10，进位为sum/10；
• 其中一个链表为空时，稍微修改一下循环，去掉另一个链表就ok了；
• 然后处理最后的进位，如果有，就建个新结点；
• return reverse(guard.next);

实现

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode h2 = reverse(head2);
        ListNode h1 = reverse(head1);
        ListNode cur = new ListNode(-1);
        ListNode guard = cur;
        int t = 0;
        while(h1 != null & h2 != null) {
            int sum = h1.val + h2.val + t;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            t = sum / 10;
            h1 = h1.next;
            h2 = h2.next;
        }
        while(h1 != null) {
            int sum = h1.val + t;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            t = sum / 10;
            h1 = h1.next;
        }
        while(h2 != null) {
            int sum = h2.val + t;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            t = sum / 10;
            h2 = h2.next;
        }
        if(t > 0) {
            cur.next = new ListNode(t);
        }
        return reverse(guard.next);
    }
    
    public ListNode reverse(ListNode node) {
        if(node == null) return null;
        ListNode cur = node;
        ListNode pre = null;
        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}