You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

The code is not very pretty, I will try to make it look better when I have time. The idea is simple, use a carry to record the carry of sum of every bit. Notice that when one of the listNode is null, you need to handle them separately. Also if there is a carry at the end of the list, you need to create a new node for it.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode p1 = l1; ListNode p2 = l2; ListNode r = l1; //result int carry = 0; while(p1.next != null) { if (p2.next != null) { int temp = (carry + p1.val + p2.val)%10; carry = (carry + p1.val + p2.val)/10; p1.val = temp; p2 = p2.next; p1 = p1.next; } else { break; } } //adding the last digit int temp = (carry + p1.val + p2.val)%10; carry = (carry + p1.val + p2.val)/10; p1.val = temp; // if p2 is null || p1 is null if (p1.next == null && p2.next == null) { if (carry == 1) { p1.next = new ListNode(1); } return r; } if (p1.next == null) { p1.next = p2.next; do{ p2 = p2.next; temp = (carry + p2.val)%10; carry = (carry + p2.val)/10; p2.val = temp; }while(p2.next != null); if (carry == 1) p2.next = new ListNode(1); return r; } if (p2.next == null) { do { p1 = p1.next; temp = (carry + p1.val)%10; carry = (carry + p1.val)/10; p1.val = temp; } while(p1.next != null); if (carry == 1) p1.next = new ListNode(1); return r; } return r; } }

The key point to remember is that when finished for head1 != null && head2 != null, use another while loop to try head1 and head2, and finally carry

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head1 = l1; ListNode head2 = l2; int carry = 0; ListNode res = new ListNode(-1); ListNode head = res; while(head1 != null && head2 != null) { head.next = new ListNode((head1.val + head2.val + carry)%10); carry = (head1.val + head2.val + carry)/10; head = head.next; head1 = head1.next; head2 = head2.next; } while (head1 != null) { head.next = new ListNode((head1.val + carry)%10); carry = (head1.val + carry)/10; head = head.next; head1 = head1.next; } while (head2 != null) { head.next = new ListNode((head2.val + carry)%10); carry = (head2.val + carry)/10; head = head.next; head2 = head2.next; } if (carry != 0) { head.next = new ListNode(carry); } return res.next; } }