描述

链表相加(二)

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。 给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0<=n,m<=10000000，链表任意值 0<=val<=9

由于数据范围过大，无法转为int相加

思路1：反转链表相加

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1 == null) {
            return head2;
        }
        if(head2 == null) {
            return head1;
        }
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        //是否需要进位
        int flag = 0;
        while(head1 != null || head2 != null) {
            int val = flag;
            if(head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            if(head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            flag = val / 10;
            cur.next = new ListNode(val % 10);
            cur = cur.next;
        }
        if(flag == 1) {
            cur.next = new ListNode(1);
        }
        //将链表反转回来，并去除哨兵节点
        return reverse(ret.next);
    }
    ListNode reverse(ListNode head) {
        ListNode pre = null;
        while(head != null) {
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
}

思路2：使用栈

使用列表存储，倒序取出也一样

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        //存Integer类型即可
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while(head1 != null) {
            stack1.push(head1.val);
            head1 = head1.next;
        }
        while(head2 != null) {
            stack2.push(head2.val);
            head2 = head2.next;
        }
        Stack<Integer> stack3 = new Stack<>();
        //进位
        int flag = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty()) {
            int val = flag;
            if(!stack1.isEmpty()) {
                val += stack1.pop();
            }
            if(!stack2.isEmpty()) {
                val += stack2.pop();
            }
            flag = val / 10;
            stack3.push(val % 10);
        }
        if(flag == 1) {
            stack3.push(1);
        }
        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        while(!stack3.isEmpty()) {
            cur.next = new ListNode(stack3.pop());
            cur = cur.next;
        }
        return ret.next;
    }
}