You are given two numbers represented in the form of linked lists. Write a program to add these two numbers and return the sum in the form of the linked list.

Problem Note:

  • The two lists given as input are not empty
  • The digits are stored in reverse order with the least significant digit (unit digit's place) as the head of the linked list.
  • The sizes of both lists may be different.
  • Both numbers do not contain leading zeroes, except if the number is zero.
  • Do not extract the digits of both lists to form the numbers, add them and split them back into nodes. Perform the addition on the list nodes.

Example 1

Input: (2->5->1) + (4->6->2)
Output: (6->1->4)
Explanation: 152 + 264 = 416

Example 2

Input: (3->8->6) + (2->3)
Output: 5->1->7
Explantion: 683 + 32 = 715

Example 3

Input: 8 + 4 (two lists with only one digit)
Output: 2->1
Explanation: 8 + 4 = 12