LeetCode(Java)の二数を加算します。
5429 ワード
テーマの説明
非負数を表す2つのチェーンテーブルを指定しました。数字はチェーンテーブルに逆方向に格納されています。
入力:(2->4->3)+(5->6->4)
出力:7->0->8
Input:(2->4->3)+(5->6->4)Output:7->0->8
問題を解く構想
(1)結果を保存するための新しいチェーンシートを構築する。
(2)臨時変数tempを設定します。
(3)入力された二つのチェーンを最初から後から同時に処理し、二つの対応する位置ごとに加算し、結果をtempに保存する。
(4)tempを10に取って、tempの個数を得て、チェーンに入れて、現在のチェーンノードを後に移動します。
(5)tempを10に対して求商し、結果を進数の値とする(10より大きい場合、商は1、進位は1;10より小さい場合、商は0、進位しない)。
注意:
(1)サイクル中に、二つのチェーンが不等長な場合を考慮する必要がある。
(2)二つのチェーンが最後まで巡回することを考慮する必要がありますが、temp=1であれば、もう一つのサイクルを行い、tempの進数をチェーンの端に加える必要があります。
コードの実装
非負数を表す2つのチェーンテーブルを指定しました。数字はチェーンテーブルに逆方向に格納されています。
入力:(2->4->3)+(5->6->4)
出力:7->0->8
:243 + 564 = 807
You are given two linked lists representing two non-negative numbers.The digits are stored in reverse order and each of their nodes contain a single digit.Add the two numbers and return it it.Input:(2->4->3)+(5->6->4)Output:7->0->8
問題を解く構想
(1)結果を保存するための新しいチェーンシートを構築する。
(2)臨時変数tempを設定します。
(3)入力された二つのチェーンを最初から後から同時に処理し、二つの対応する位置ごとに加算し、結果をtempに保存する。
(4)tempを10に取って、tempの個数を得て、チェーンに入れて、現在のチェーンノードを後に移動します。
(5)tempを10に対して求商し、結果を進数の値とする(10より大きい場合、商は1、進位は1;10より小さい場合、商は0、進位しない)。
注意:
(1)サイクル中に、二つのチェーンが不等長な場合を考慮する必要がある。
(2)二つのチェーンが最後まで巡回することを考慮する必要がありますが、temp=1であれば、もう一つのサイクルを行い、tempの進数をチェーンの端に加える必要があります。
コードの実装
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode res = new ListNode(-1);
ListNode cur = res;
int temp = 0;
while (l1 != null || l2 != null || temp != 0) {
if (l1 != null) {
temp += l1.val;
l1 = l1.next;
}
if (l2 != null) {
temp += l2.val;
l2 = l2.next;
}
cur.next = new ListNode(temp % 10);
cur = cur.next;
temp = temp / 10;
}
return res.next;
}
}