LeetCode题解-445. 两数相加 II

题目描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例1:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

输出: 7 -> 8 -> 0 -> 7

解题思路

因为要从最后一节点开始相加，但是链表的最后一个节点不好获得，所以自然想到先把两条翻转，然后进行相加，最后把相加后的链表再次翻转即可。

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        // 翻转链表
        ListNode r1 = reverse(l1);
        ListNode r2 = reverse(l2);
        ListNode dummy = new ListNode(-1);
        ListNode nHead = dummy;
        // 进位标志
        boolean flag = false;
        while (r1 != null || r2 != null) {
            int val = (r1 != null ? r1.val : 0) + (r2 != null ? r2.val : 0);
            if (flag) {
                val += 1;
            }
            // 如果当前两个节点相加大于9，则在下一次相加计算时要加1
            if (val > 9) {
                dummy.next = new ListNode(val - 10);
                flag = true;
            } else {
                dummy.next = new ListNode(val);
                flag = false;
            }
            if (r1 != null) {
                r1 = r1.next;
            }
            if (r2 != null) {
                r2 = r2.next;
            }
            dummy = dummy.next;
        }
        // 当两条链表都遍历完了，如果还有进位，需要补1
        if (flag) {
            dummy.next = new ListNode(1);
        }
        return reverse(nHead.next);
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

##进阶思路
如果不能对链表中的节点进行翻转的话，则考虑用栈先进后出的特性，也可以实现从最后一位开始相加。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       if (l1 == null) return l2;
       if (l2 == null) return l1;
       Stack<Integer> s1 = toStack(l1);
       Stack<Integer> s2 = toStack(l2);
       boolean flag = false;
       ListNode dummy = new ListNode(-1);
       ListNode nHead = dummy;
       while (!s1.isEmpty() || !s2.isEmpty()) {
           int val = (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
           if (flag) {
               val += 1;
           }
           // 如果当前两个节点相加大于9，则在下一次相加计算时要加1
           if (val > 9) {
               dummy.next = new ListNode(val - 10);
               flag = true;
           } else {
               dummy.next = new ListNode(val);
               flag = false;
           }
           dummy = dummy.next;
       }
       if (flag) {
           dummy.next = new ListNode(1);
       }
       return reverse(nHead.next);
   }

   public Stack<Integer> toStack(ListNode head) {
       Stack<Integer> stack = new Stack<>();
       while (head != null) {
           stack.push(head.val);
           head = head.next;
       }
       return stack;
   }
   
   public ListNode reverse(ListNode head) {
       if (head == null || head.next == null) {
           return head;
       }
       ListNode prev = null;
       ListNode cur = head;
       while (cur != null) {
           ListNode next = cur.next;
           cur.next = prev;
           prev = cur;
           cur = next;
       }
       return prev;
   }