"質問：2つの「非負」整数を表すために2つの「空でない」連結リストが与えられます。それぞれの数字は「逆」順序で格納され、各ノードには1つの数字しか格納できません。2つの数値を足し合わせると、その和を表す新しい連結表が返されます。これらの数値はどちらも「0」から始まらないと仮定できます。
"
例
入力： (2) -> 4 -> 3) + (5 -> 6 -> 4)
出力：7 -> 0 -> 8
= 807
問題解決のアイデア
"この問題では、それぞれの数字が連鎖表に逆順に格納されていると書かれていますが、実際には、足し算の操作は最初の数字から足し算で行われ、前から後ろへの連鎖表は下の数字から始まるため、難易度は下がります。
"
それは合計なので、それは難しいことではありません、2つのチェーンの各ノードを取り出し、次に合計し、10より大きい場合は、四捨五入1をマークし、残りは10の合計を取る、結果はチェーンテーブルの最初の有効なノードのターゲットであり、図に示すように、具体的なプロセス：
実現プロセス：
1、中核となる方法は、2つのリストをトラバースし、ノードごとに合計することです。
- 必要な2つの和の連鎖表のノード数は不明なので、whileループが選択されます。ループは、リンクされたリストのいずれかのノードがNULLでない限り続ける必要があります。
- しかし、四捨五入のケースがあるため、四捨五入が0でない場合でもループを止めることはできません。
2.合計の結果を格納する新しいチェーンテーブルを生成します。
- チェーンテーブルの問題については、通常、フラグノードを作成し、それは特定の値を格納しない、その次は、主に得られたターゲットチェーンテーブルの復帰を容易にするために、最初の有効なノードを指すための責任があります。
- 同時に、各ノードの生成を担当するカレント・ノードを作成する必要があります。カレント・ノードは移動可能で、生成された各ノードに対して1ノード戻る必要があります。
言語表現能力が少し乏しく、あまり明確に記述されていないかもしれませんが、コードには必要なコメントがあります。
コードの実装
class ListNode
{
public $val = 0;
public $next = null;
public function __construct($val)
{
$this->val = $val;
}
}
class LeetCode002
{
/**
* @param ListNode $l1
* @param ListNode $l2
* @return ListNode
*/
public function addTwoNumbers($l1, $l2)
{
if ($l1 == null && $l2 == null) {
return null;
}
$tag = new ListNode(0);//空のノードを作成する
$current = $tag;
$addOne = 0;//
while ($l1 != null
$l2 != null
$addOne != 0) {
$val1 = $l1 == null ? 0 : $l1->val;
$val2 = $l2 == null ? 0 : $l2->val;
$sum = $val1 + $val2 + $addOne;
$current->next = new ListNode($sum % 10);
$current = $current->next;
$addOne = intval($sum / 10);//ピット、強く型付けされた言語にはこの問題はない
if ($l1 != null) {
$l1 = $l1->next;
}
if ($l2 != null) {
$l2 = $l2->next;
}
}
return $tag->next;
}
}
//Test Case
$leetCode = new LeetCode002();
$l1 = new ListNode(2);
$l1->next = new ListNode(4);
$l2 = new ListNode(5);
$l2->next = new ListNode(6);
$newList = $leetCode->addTwoNumbers($l1, $l2);
$str = '';
while ($newList != null) {
$str .= $newList->val.'->';
$newList = $newList->next;
}
echo $str;
実施結果
