LCR 025

题目：LCR 025

解法一：反转链表

反转两个链表，然后顺序遍历，并相加进位，最后反转结果

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0), resNode = dummy, temp;l1 = reverseList(l1);l2 = reverseList(l2);int num = 0;while (l1 != null || l2 != null || num == 1) {if (l1 == null && l2 != null) num += l2.val;else if (l1 != null && l2 == null) num += l1.val;else if (l1 != null && l2 != null) num += l1.val + l2.val;temp = new ListNode(num % 10);resNode.next = temp;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;resNode = resNode.next;num /= 10;}return reverseList(dummy.next);}

解法二：栈

将两链表压入栈中，然后顺序遍历两栈，相加并进位

注意：遍历栈时，每个新节点指向上一个节点，而非下一个节点

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Deque<Integer> stack1 = new LinkedList();Deque<Integer> stack2 = new LinkedList();while (l1 != null || l2 != null) {if (l1 != null) {stack1.push(l1.val);l1 = l1.next;}if (l2 != null) {stack2.push(l2.val);l2 = l2.next;}}ListNode prev, curr = null;int num = 0;while (!stack1.isEmpty() || !stack2.isEmpty() || num != 0) {if (stack1.isEmpty() && !stack2.isEmpty()) num += stack2.pop();else if (stack2.isEmpty() && !stack1.isEmpty()) num += stack1.pop();else if (!stack1.isEmpty() && !stack2.isEmpty()) num += stack1.pop() + stack2.pop();prev = new ListNode(num % 10);prev.next = curr;curr = prev;num /= 10;}return curr;}