Description
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Setup
In LeetCode, the linked list is provided for you. We’ll have to add that ourselves. To make the test cases more readable, we will also add a ToString to print it out, and a factory to easily create it from an array of integers.
class ListNode;
begin
constructor Init(Value : Integer, Next : ListNode := Nil);
begin
this.Value := Value;
this.Next := Next;
end
function ToString() : String;
begin
var ToString := Str('[') + Value;
var Current := Next;
while Current <> Nil do
begin
ToString := ToString + ', ' + Current.Value;
Current := Current.Next;
end
ToString := ToString + ']';
Exit ToString;
end
end
function LinkedList(Values : Array of Integer) : ListNode;
var
Head, Current : ListNode;
begin
if Values.Length = 0 then raise 'Must contain at least one node!';
Head := ListNode(0);
Current := Head;
for var I := Iterator(Values); I.HasNext() do
begin
Current.Next := ListNode(I.Next());
Current := Current.Next;
end
Exit Head.Next;
end
Tests
With that taken care of, we can add the 3 example scenarios as test cases:
test 'Case #1';
begin
var Sum := AddTwoNumbers([2, 4, 3], [5, 6, 4]);
AssertEqual('[7, 0, 8]', Sum.ToString());
end
test 'Case #2';
begin
var Sum := AddTwoNumbers([0], [0]);
AssertEqual('[0]', Sum.ToString());
end
test 'Case #3';
begin
var Sum := AddTwoNumbers([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9]);
AssertEqual('[8, 9, 9, 9, 0, 0, 0, 1]', Sum.ToString());
end
Solution
To get a O(n) solution, you just loop through the two linked lists at the same time, and add the two together. If the first or second node is Nil you set that value to 0.
Probably the hardest part of this problem is carrying to 10’s place. You can use division to get the value, and the mod operator to get the carry. The tricky part comes in modifying the while loop to make sure you continue till carry value is gone, even if it goes beyond both linked lists.
Note: it makes the solution easier by creating a dummy head, and just returning the Next property.
function AddTwoNumbers(List1, List2: ListNode) : ListNode;
var
Head, Current : ListNode;
First, Second : Integer;
Sum, Carry : Integer := 0;
begin
Head := ListNode(0, Nil);
Current := Head;
while List1 <> Nil Or List2 <> Nil Or Carry <> 0 do
begin
First := List1 = Nil ? 0 : List1.Value;
Second := List2 = Nil ? 0 : List2.Value;
Sum := First + Second + Carry;
Carry := Sum / 10;
Current.Next := ListNode(Sum % 10);
Current := Current.Next;
List1 := List1?.Next;
List2 := List2?.Next;
end
Exit Head.Next;
end
**********
Bonus
Using operator overloading the code becomes more readable:
operator + (Other : ListNode) : ListNode; begin Exit AddTwoNumbers (this, Other); end
Now the code looks like LinkedList([1, 2, 3]) + LinkedList([4, 5, 6]).
Bonus #2
In an interview the other day I had the good old “reverse a linked list” coding question, in Java of course, but here is the equivalent in Algol-24 😀
/// Add to ListNode class.
///
function Reverse() : ListNode;
var
Current, Previous, Next : LinkedNode := Nil;
begin
Current := this;
while Current <> Nil do
begin
Next := Current.Next;
Current.Next := Previous;
Previous := Current;
Current := Next;
end
Exit Previous;
end
test 'Reverse a linked list';
begin
var TheList := LinkedList([2, 4, 3]);
var Sum := TheList.Reverse();
AssertEqual('[3, 4, 2]', Sum.ToString());
end
Leave a Reply