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. * struct ListNode { * int val; * struct ListNode *next; * }; */ int getListLength(const struct ListNode *l){ struct ListNode *pNode = l; int count = 0; while(pNode){ count++; pNode = pNode->next; } return count; } int addTwoNumbers_1(struct ListNode *l1,int len1,struct ListNode *l2,int len2){ int carry = 0; int sum = 0; if(len1 == 0 || len2 == 0|| l1 == NULL || l2 == NULL){ return 0; } if(len1>len2){ carry = addTwoNumbers_1(l1->next,len1-1,l2,len2); sum = carry + l1->val; l1->val = sum; } if(len1 == len2){ carry = addTwoNumbers_1(l1->next,len1-1,l2->next,len2-1); sum = carry + l1->val + l2->val; l1->val = sum; } if(len1<len2){ carry = addTwoNumbers_1(l1,len1,l2->next,len2-1); sum = carry + l2->val; l2->val = sum; } carry = sum/10; return carry; } struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { int len1 = 0; int len2 = 0; int carry = 0; struct ListNode *pNode = NULL; struct ListNode *head = NULL; len1 = getListLength(l1); len2 = getListLength(l2); if(len1>len2){ carry = addTwoNumbers_1(l1,len1,l2,len2); pNode = l1; } if(len1<=len2){ carry = addTwoNumbers_1(l2,len2,l1,len1); pNode = l2; } if(carry>0){ head = (struct ListNode *)malloc(sizeof(struct ListNode)); head->val = carry; head->next = pNode; pNode = head; } return pNode; } /*java solution using stack*/ public class Solution { 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 sum = 0; ListNode list = new ListNode(0); while (!s1.empty() || !s2.empty()) { if (!s1.empty()) sum += s1.pop(); if (!s2.empty()) sum += s2.pop(); list.val = sum % 10; ListNode head = new ListNode(sum / 10); head.next = list; list = head; sum /= 10; } return list.val == 0 ? list.next : list; } }