leetcode445

题目要求

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

对以链表形式的两个整数进行累加计算。

思路一：链表转置

链表形式跟非链表形式的最大区别在于我们无法根据下标来访问对应下标的元素。假如我们希望从后往前对每个位置求和，则必须每次都从前往后访问到对应下标的值才可以。因此这里通过先将链表转置，再从左往右对每一位求和来进行累加。

链表的转置的方法如下：

假设链表为1->2->3
则为其设置一个伪头：dummy->1->2->3， 并且记录当前需要交换的元素为cur
则每次转置如下：
dummy->1(cur)->2->3
dummy->2->1(cur)->3
dummy->3->2->1(cur)

代码如下：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode rl1 = reverse(l1);
    ListNode rl2 = reverse(l2);
    ListNode result = new ListNode(0);
    int carry = 0;
    while(rl1 != null || rl2 != null || carry != 0) {
        int add = (rl1 == null ? 0 : rl1.val)
                + (rl2 == null ? 0 : rl2.val)
                + carry;
        carry = add / 10;
        ListNode tmp = new ListNode(add % 10);
        tmp.next = result.next;
        result.next = tmp;
        rl1 = rl1==null? rl1 : rl1.next;
        rl2 = rl2==null? rl2 : rl2.next;
    }
    return result.next;
}

public ListNode reverse(ListNode l) {
    ListNode dummy = new ListNode(0);
    dummy.next = l;
    ListNode cur = l;
    while(cur!= null && cur.next != null) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = dummy.next;
        dummy.next = next;
    }
    return dummy.next;
}

思路二： 栈

如果不希望改变链表的结构，那么用什么方式来将链表中的元素按照倒序读取呢？这时候就可以很快的联想到栈这个结构。通过栈可以实现先进后出，即读取顺序的转置。代码如下：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();
    while(l1 != null) {
        s1.push(l1.val);
        l1 = l1.next;
    };
    while(l2 != null) {
        s2.push(l2.val);
        l2 = l2.next;
    }
    
    int carry = 0;
    ListNode result = new ListNode(0);
    while(!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
        int add = (s1.isEmpty() ? 0 : s1.pop())
                + (s2.isEmpty() ? 0 : s2.pop())
                + carry;
        carry = add / 10;
        ListNode tmp = new ListNode(add % 10);
        tmp.next = result.next;
        result.next = tmp;
    }
    return result.next;
}