Problem
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
Solution
One solution is to reverse the 2 linked list, then traversal them and create the result linked list. Finally we reverse the result linked list in order to output the final result.
This approach will have time complexity O(N1 + N2) for we reversed the original linked lists which is N1+N2, then we iterate the linked lists to create the result, the cost is max(N1, N2), then we reverse the result, which cost max(N1, N2). If we reverse the original linked list in place, we don't have to use extra space in this approach. The space complexity is O(1).
For the follow up question, we can not reversing the lists. Then we can convert the two linked lists into two numbers, then we add up the 2 numbers. Finally we convert the sum into a linked list. Please compare with a similar problem reverse an integer for the converting technique used here.
As a note, if we have to convert linked list into integer and sum them up, we could run into the problem of overflow. If the linked list is long, we need to use java.math.BigInteger instead of simple %, /, *, + operations used here.
class Solution {
public static void main(String[] args) {
//(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Node head1 = new Node(7, new Node(2, new Node(4, new Node(3, null))));
Node head2 = new Node(5, new Node(6, new Node(4, null)));
Node result = solve(head1, head2);
while(result != null) {
System.out.print(result.val + "->");
result = result.next;
}
System.out.println("null");
}
//(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
private static Node solve(Node head1, Node head2) {
int a = convertToInt(head1);
int b = convertToInt(head2);
int c = a + b; //7243 + 564 = 7807
return convertToLinkedList(c);
}
//7 -> 2 -> 4 -> 3
private static int convertToInt(Node head) {
int result = 0;
while(head != null) {
result = result * 10 + head.val;
head = head.next;
}
return result;
}
//7807
private static Node convertToLinkedList(int c) {
Node pre = null;
Node cur = null;
int lsb = 0;
//7->8->0->7->null
while(c > 0) {
pre = cur;
lsb = c%10; //7
cur = new Node(lsb, pre);
c = c/10;
}
return cur;
}
static class Node {
private int val;
private Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
}
The time complexity is O(N1+N2), the space complexity is O(1).
If we use BigInteger, the time complexity and space complexity depends on the implementation of BigInteger, which could change algorithm according to the size of the number.
