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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    // Solution 1: Two pointers, O(n) time, O(1) space
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // get length
        int len1 = getLen(l1);
        int len2 = getLen(l2);
        // make l1 the longer one
        if (len2 > len1) {
            ListNode temp = l1;
            l1 = l2;
            l2 = temp;
        }
        int dif = Math.abs(len1 - len2);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode left = dummy;
        // add copy longer part to new list
        while (dif > 0) {
            cur.next = new ListNode(l1.val);
            if (l1.val != 9) {
                // left = cur.next, not l1
                left = cur.next;
            }
            cur = cur.next;
            l1 = l1.next;
            dif--;
        }
        // add two equal length list
        while (l1 != null) {
            int val = l1.val + l2.val;
            if (val > 9) {
                val = val % 10;
                left.val += 1;
                while (left.next != null) {
                    left.next.val = 0;
                    left = left.next;
                }
            }
            cur.next = new ListNode(val);
            if (val != 9) {
                left = cur.next;
            }
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        // return
        return dummy.val == 1 ? dummy : dummy.next;
    }
    
    public int getLen(ListNode node) {
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }
        return len;
    }
/**
    // Solution 2: Stack
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while (l1 != null && l2 != null) {
            s1.push(l1);
            s2.push(l2);
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            s1.push(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2);
            l2 = l2.next;
        }
        ListNode head = null;
        int carry = 0;
        
        while (!s1.isEmpty() && !s2.isEmpty()) {
            int val1 = s1.pop().val;
            int val2 = s2.pop().val;
            ListNode newNode = new ListNode((val1 + val2 + carry) % 10);
            carry = (val1 + val2 + carry) / 10;
            newNode.next = head;
            head = newNode;
        }
        while (!s1.isEmpty()) {
            int val1 = s1.pop().val;
            ListNode newNode = new ListNode((val1 + carry) % 10);
            carry = (val1 + carry) / 10;
            newNode.next = head;
            head = newNode;
        }
        while (!s2.isEmpty()) {
            int val2 = s2.pop().val;
            ListNode newNode = new ListNode((val2 + carry) % 10);
            carry = (val2 + carry) / 10;
            newNode.next = head;
            head = newNode;
        }
        if (carry == 1) {
            ListNode node = new ListNode(1);
            node.next = head;
            head = node;
        }
        return head;
    }
*/
/**
    // Solution 3: reverse linkedlist
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Reverse l1 and l2
        l1 = reverse(l1);
        l2 = reverse(l2);
        // add
        ListNode ptr1 = l1;
        ListNode ptr2 = l2;
        int carry = 0;
        ListNode head = null;
        
        while (ptr1 != null && ptr2 != null) {
            int val1 = ptr1.val;
            int val2 = ptr2.val;
            ListNode newNode = new ListNode((val1 + val2 + carry) % 10);
            carry = (val1 + val2 + carry) / 10;
            newNode.next = head;
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
            head = newNode;
        }
        while (ptr1 != null) {
            ListNode newNode = new ListNode((ptr1.val + carry) % 10);
            newNode.next = head;
            carry = (ptr1.val + carry) / 10;
            ptr1 = ptr1.next;
            head = head.next;
            head = newNode;
        }
        while (ptr2 != null) {
            ListNode newNode = new ListNode((ptr2.val + carry) % 10);
            newNode.next = head;
            carry = (ptr2.val + carry) / 10;
            ptr2 = ptr2.next;
            head = head.next;
            head = newNode;
        }
        
        // Reverse back
        reverse(l1);
        reverse(l2);
        
        if (carry == 1) {
            ListNode node = new ListNode(1);
            node.next = head;
            head = node;
        }
        return head;
    }
    public ListNode reverse(ListNode node) {
        ListNode pre, cur, next;
        pre = null;
        cur = node;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
*/

    /**
     * Solution 1: First take care of l1, which is longer.
     * Then take care of l1 and l2.
     * right points to the first non 9 node counted from right side.
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = getLen(l1);
        int len2 = getLen(l2);
        int dif = Math.abs(len1 - len2);
        if (len2 > len1) {
            ListNode temp = l1;
            l1 = l2;
            l2 = temp;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode right = cur;
        
        while (dif > 0) {
            cur.next = new ListNode(l1.val);
            if (l1.val != 9) {
                right = cur.next;
            }
            cur = cur.next;
            l1 = l1.next;
            dif -= 1;
        }
        
        while (l1 != null) {
            int val = l1.val + l2.val;
            if (val > 9) {
                val = val % 10;
                right.val += 1;
                while (right.next != null) {
                    right.next.val = 0;
                    right = right.next;
                }
            }
            cur.next = new ListNode(val);
            if (val != 9) {
                right = cur.next;
            }
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        return dummy.val == 1 ? dummy : dummy.next;
    }
    
    private int getLen(ListNode node) {
        int counter = 0;
        while (node != null) {
            node = node.next;
            counter++;
        }
        return counter;        
    }
    */
}

Reference:
http://www.cnblogs.com/grandyang/p/6216480.html

这道题是之前那道Add Two Numbers的拓展,我们可以看到这道题的最高位在链表首位置,如果我们给链表翻转一下的话就跟之前的题目一样了,这里我们来看一些不修改链表顺序的方法。由于加法需要从最低位开始运算,而最低位在链表末尾,链表只能从前往后遍历,没法取到前面的元素,那怎么办呢?我们可以利用栈来保存所有的元素,然后利用栈的后进先出的特点就可以从后往前取数字了,我们首先遍历两个链表,将所有数字分别压入两个栈s1和s2中,我们建立一个值为0的res节点,然后开始循环,如果栈不为空,则将栈顶数字加入sum中,然后将res节点值赋为sum%10,然后新建一个进位节点head,赋值为sum/10,如果没有进位,那么就是0,然后我们head后面连上res,将res指向head,这样循环退出后,我们只要看res的值是否为0,为0返回res->next,不为0则返回res即可

下面这种方法使用递归来实现的,我们知道递归其实也是用栈来保存每一个状态,那么也就可以实现从后往前取数字,我们首先统计出两个链表长度,然后根据长度来调用递归函数,需要传一个参数差值,递归函数参数中的l1链表长度长于l2,在递归函数中,我们建立一个节点res,如果差值不为0,节点值为l1的值,如果为0,那么就是l1和l2的和,然后在根据差值分别调用递归函数求出节点post,然后要处理进位,如果post的值大于9,那么对10取余,且res的值自增1,然后把pos连到res后面,返回res,最后回到原函数中,我们仍要处理进位情况

下面这种方法借鉴了Plus One Linked List中的解法三,在处理加1问题时,我们需要找出右起第一个不等于9的位置,然后此位置值自增1,之后的全部赋为0。这里我们同样要先算出两个链表的长度,我们把其中较长的放在l1,然后我们算出两个链表长度差diff。如果diff大于0,我们用l1的值新建节点,并连在cur节点后(cur节点初始化时指向dummy节点)。并且如果l1的值不等于9,那么right节点也指向这个新建的节点,然后cur和l1都分别后移一位,diff自减1。当diff为0后,我们循环遍历,将此时l1和l2的值加起来放入变量val中,如果val大于9,那么val对10取余,right节点自增1,将right后面节点全赋值为0。在cur节点后新建节点,节点值为更新后的val,如果val的值不等于9,那么right节点也指向这个新建的节点,然后cur,l1和l2都分别后移一位。最后我们看dummy节点值若为1,返回dummy节点,如果是0,则返回dummy的下一个节点。

Advertisements