両方のリストの長さを数えます。先頭に短いリストを0桁の数字で埋めて、長さが等しくなるようにします。今度は、両方の数字を余分な0で埋めます（最初の数字のキャリーで使用されるので、9 + 1 = 10となる可能性があります）。 前の2つの長さの3番目のリンクされたリストを作成します。
class Digit
{
public:
Digit *Next;
int Dt;
}
と、このような機能：：
- これは、 "バージョン0" である
今、あなたは、このようなクラスを行います。
- "バージョン1"では、最後のキャリーの余分なパディングを削除し、必要な場合にのみ追加します。
- "バージョン2"では、リンクされたリストの先頭から不要な "0"桁を削除します。
- "バージョン3"では、
runningTotalリンクリストをSumに直接作成します。あなたは第1レベルにランニングトータルの「ヘッド」だけを合計します。
- より短いLLを埋め込むのではなく、 "バージョン4"では、最も長いLLからスキップするための桁数のパラメータを渡します（これは最も困難な通過です）。
さらに複雑な可能性がありますが、リストの長さを事前にカウントする必要はありません。
第1の再帰関数は、両方が存在するときに単に左右に移動するだけです。両方が同時に終了した場合は、前の例のように単純にロールバックすることができます。
それらの一方が他方の前に終了した場合、あなたはこのような別の再帰関数を使用（* extraDigitsの初期値は1）：
この機能は最終的に返す
void SaveRemainingDigits(const Digit *remaining, int *extraDigits, int **buffer)
{
int currentDigit = *extraDigits - 1;
*extraDigits = *extraDigits + 1;
if (remaining->Next)
{
SaveRemainingDigits(remaining->Next, extraDigits, buffer);
}
else
{
*buffer = (int*)malloc(sizeof(int) * extraDigits);
}
(*buffer)[currentDigit] = remaining->Dt;
}
、我々はスクラッチパッドからを持っていますどこの数字とスクラッチパッドの長さを抽出するか
私たちの最初の再帰関数の最下位レベルは、最短のリンクリストの現在の桁とスクラッチパッドの最後の桁を合計し、最も長いちょうど使用された数字の代わりにスクラッチパッド内のリンクされたリスト。これで、再帰関数をアンロールし、スクラッチパッドを円形配列として使用します。アンロールを終了すると、要素をスクラッチパッドから直接取り出して実行中のリンクリストに追加します。
私が言ったように、少し複雑ですが、1〜2時間でプログラムとして書き留めることができました。 （キャリーなし）
例
1 2 3 4
6 5
あなたが最初の2つの要素を再帰的に。だから、
1-6 (in the first level)
2-5 (in the second level)
は今、あなたは第二のリストが終了したことを見ていると、あなたは第2の機能を使用します。
3 (extraDigit enters as 0, is modified to 1. currentDigit = 0)
4 (extraDigit enters as 1, is modified to 2. currentDigit = 1.
malloc of 2 elements,
buffer[currentDigit] = 4 => buffer[1] = 4)
unroll and we return to the previous row
3 (currentDigit = 0
buffer[currentDigit] = 3 => buffer[0] = 3)
は、今、私たちはその後、リストを反復私は、私はから始まったノードのアドレスを格納する*ヘッドまたは*尻尾のようなノードを作成していた以前の機能に
2-5 (in the second level,
with a lengthBuffer == 2,
we set index = length(buffer) - 1
currentDigitTotal = 5 + buffer[index] => currentDigitTotal = 5 + 4
buffer[index] = 2 => buffer[1] = 2;
index = (index - 1 + lengthBuffer) % lengthBuffer => index = 0
1-6 (in the first level,
with a lengthBuffer == 2,
index = 0,
currentDigitTotal = 6 + buffer[index] => currentDigitTotal = 6 + 3
buffer[index] = 1 => buffer[0] = 1;
index = (index - 1 + lengthBuffer) % lengthBuffer => index = 1
now we exited the recursive function.
In an external function we see that we have a buffer.
We add its elements to the head of the total.
Our Linked list now is 9-9 and our buffer is 1,2 with index 1
for (int i = 0; i < lengthBuffer; i++)
{
runningTotal.AddHead(buffer(index));
index = (index - 1 + lengthBuffer) % lengthBuffer
}
Cの質問のように聞こえます。なぜ再帰??? –
あなたは正確に何を計算するつもりでしたか？ l1 [0] + l2 [0] - > l3 [0]、またはl1 [0] + l1 [私は本当にそれを取得しない;） –
それはあなたのインタビュアーがばかだと示しています。それを再帰的に行うことは、少なくともリストの長さを1回カウントすることと同じくらい遅いです。リストを直接逆にする代わりに、スタックを逆のリストとして使用したいと考えています。あなたが望むなら、私はコードを書くことができますが、この時点ではかなり明確にすべきです。 – xanatos