LeetCodeブラシノート——チェーンテーブルの和を求める問題

チェーンテーブルの和の問題
テーマ:面接問題02.05.チェーンテーブルは、チェーンテーブルで表される2つの整数を求め、各ノードは1つの数ビットを含む.これらの数桁は逆方向に格納され、すなわちチェーンテーブルの先頭に位置している.関数を記述してこの2つの整数を合計し、チェーンテーブル形式で結果を返します.

  ：
  ：(7 -> 1 -> 6) + (5 -> 9 -> 2)， 617 + 295
  ：2 -> 1 -> 9， 912
  ：            ，     。

考え方:チェーンテーブルの数字が低位で前に保管されている場合、チェーンテーブルの皆さんが位置合わせされているので、直接ビットで加算すればいいです.ここでは、スペースの複雑さを低減するために、結果を長いチェーンテーブルに保存することを選択します.そこでまず2つのチェーンテーブルを巡り,それぞれその長さを求める.加算を計算するときに、sumという2つの変数を設定します.1つは一時和を格納し、もう1つはadcで、キャリーを格納します.
境界の状況を考慮:

2 2 2つのチェーンテーブルの長さが異なる場合、チェーンテーブルが空であるかadcが0

になるまで、キャリーと長いチェーンテーブルを加算する必要があります.

チェーンテーブルの処理が完了したが、adcがある場合は、キャリーを格納するために新しいノードを作成する必要があります.(したがって、前の計算の過程で、結果チェーンテーブルの最後の要素ポインタを記録しました.)

くだらないことを言って、眠くなって、直接コードをつけます:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1=0,len2=0;
        ListNode* p1=l1,*p2=l2,*reshead=l1,*tail;
        while(p1){
            p1=p1->next;
            len1++;
        }
        while(p2){
            p2=p2->next;
            len2++;
        }
        
        if(len1<len2){
            p1=l2;
            reshead=l2;
            p2=l1;
        }
        else{
            p1=l1;
            p2=l2;
        }
        int sum=0;
        int adc=0;
        while(p2){
            sum=p1->val+p2->val+adc;
            adc=sum/10;
            p1->val=sum%10;
            tail=p1;
            p1=p1->next;
            p2=p2->next;
        }
        while(p1&&adc){
            sum=p1->val+adc;
            adc=sum/10;
            p1->val=sum%10;
            tail=p1;
            p1=p1->next;
        }
        if(adc){
            tail->next=new ListNode(adc);
        }
        return reshead;
    }
};

ステップアップ:チェーンテーブルの整数が順方向に格納されている場合の処理方法