Skip to content

Instantly share code, notes, and snippets.

@charlespunk
Created February 13, 2013 13:49
Show Gist options
  • Save charlespunk/4944714 to your computer and use it in GitHub Desktop.
Save charlespunk/4944714 to your computer and use it in GitHub Desktop.
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stores in reverse order, such
that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
public static Node addReverseOrderList(Node firstNumber, Node secondNumber){
return addReverseOrderList(firstNumber, secondNumber, 0);
}
public static Node addReverseOrderList(Node firstNumber, Node secondNumber, int carry){
if(firstNumber == null && secondNumber == null){
if(carry == 1) return new Node(1);
else return null;
}
int sum = 0;
if(firstNumber != null) sum += firstNumber.value;
if(secondNumber != null) sum += secondNumber.value;
sum += carry;
Node nextNode = addReverseOrderList(
firstNumber != null ? firstNumber.next : null,
secondNumber != null ? secondNumber.next : null,
sum >= 10 ? 1 : 0);
Node thisNode = new Node(sum % 10);
thisNode.next = nextNode;
return thisNode;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment