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

 

 

M1: 先把两个链表反转，相加之后再反转

time: O(n), space: O(n)

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode dummy = new ListNode(0);        ListNode prehead = dummy;        int remainder = 0;        ListNode p1 = reverse(l1), p2 = reverse(l2);        while(p1 != null || p2 != null) {            int sum = remainder;            if(p1 != null) {                sum += p1.val;                p1 = p1.next;            }            if(p2 != null) {                sum += p2.val;                p2 = p2.next;            }            dummy.next = new ListNode(sum % 10);            remainder = sum / 10;            dummy = dummy.next;        }        if(remainder != 0) {            dummy.next = new ListNode(remainder);        }        ListNode res = reverse(prehead.next);        return res;    }        private ListNode reverse(ListNode head) {        ListNode prev = null, cur = head;        while(cur != null) {            ListNode nextnode = cur.next;            cur.next = prev;            prev = cur;            cur = nextnode;        }        return prev;    }}

 

M2: follow-up 不能反转链表

用两个stack分别存储链表元素，再相加。

注意如果相加的话，得到的结果是反的，所以在相加的时候，就要边反转此结果链表

detail: 把dummy的值设为sum%10，tmp是新节点，其值为carry，tmp指向dummy，然后dummy向前移动一位，即dummy = tmp

最后还要判断一下leading number是不是0，如果为0，则返回下一个节点

time: O(n), space: O(n)

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        Stack
     
       s1 = new Stack<>();        Stack
      
        s2 = new Stack<>();        while(l1 != null) {            s1.push(l1.val);            l1 = l1.next;        }        while(l2 != null) {            s2.push(l2.val);            l2 = l2.next;        }                ListNode head = new ListNode(0);        int carry = 0;        while(!s1.isEmpty() || !s2.isEmpty()) {            int sum = carry;            if(!s1.isEmpty()) {                sum += s1.pop();            }            if(!s2.isEmpty()) {                sum += s2.pop();            }            head.val = sum % 10;            ListNode newHead = new ListNode(sum / 10);            newHead.next = head;            head = newHead;            carry = sum / 10;        }                return head.val != 0 ? head : head.next;    }}