[数据结构与算法]关于求和问题 右侧对齐

我们先来看一个简单题

?思路： 我们大多数人看到这个题肯定想把字符串转化为数字 然后进行一顿操作（x）

因为字符串所表示的数的大小可能会大于int double longlong类型所能表示范围

正确思路 我们应该进行右侧对齐 然后设置一个变量判断是否有进位 然后返回

3//代码实现

class Solution {
public:
? ? string addBinary(string a, string b) {
? ? ? ? ?string res="";
? ? ? ? int n=a.size()-1;
? ? ? ? int m=b.size()-1;
? ? ? ? int ?pre=0;//是否有向前进位
? ? ? ? int cur=0;
? ? ? ? while(n>=0 || m>=0){
? ? ? ? ? ??
? ? ? ? ? ? int cur =(n>=0?a[n]-'0':0)+(m>=0?b[m]-'0':0)+pre;
? ? ? ? ? ? res+=cur%2==0?'0':'1';
? ? ? ? ? ? pre=cur/2;
? ? ? ? ? ? n--;
? ? ? ? ? ? m--;
? ? ? ? ? ??
? ? ? ? }
? ? ? ? if(pre!=0){
? ? ? ? ? ? res+=pre+'0';
? ? ? ? }
? ? ? ? ? reverse(res.begin(),res.end());
? ? ? ? return res;
? ? }
};?

?

二

如果把这个字符串改成链表应该如何操作呢

?我们还是一样的思路 我们还是从低位开始计算 我们应该 先把链表翻转 然后把计算结果进行再次翻转然后返回就得到了正确答案

思路 1.进行把两个链表进行翻转//??https://leetcode-cn.com/problems/reverse-linked-list/

? ? ? ? ?2.然后进行跟上一道题一样的操作

1.如何翻转链表?

代码实现：

  ListNode* reversList(ListNode *head){
        if(head==NULL) return NULL;
        ListNode*cur=head;
        ListNode* pre=NULL;
        while(cur!=NULL){
            ListNode *pnext=cur->next;
            cur->next=pre;
            pre=cur;
            cur=pnext;
        }
        return pre; 
    }

2.然后进行操作

   ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //右侧对齐
     ListNode*r1=reversList(l1);
     ListNode*r2=reversList(l2);
     ListNode *dummy=new ListNode(0);
        ListNode* cur=dummy;
        int sum=0;
        int carry=0;//记录进位问题
      while(r1!=NULL || r2!=NULL)
      {
          cur->next = new ListNode(0);//新建节点
          cur = cur->next;
          int n1=0;
          if(r1!=NULL){
              n1=r1->val;
              r1=r1->next;
          }
             int n2=0;
              if(r2!=NULL){
                  n2=r2->val;
                  r2=r2->next;
              }
          sum=n1+n2+carry;
          carry=sum/10;
          cur->val=sum%10;
      }
        if(carry)
        {
            cur->next=new ListNode(1);
        }
        ListNode *r3=dummy->next;
       delete dummy;
        dummy = nullptr;
        ListNode* l3 = reversList(r3);
        return l3;
    }
};

这里应用了虚拟头结点需要接下来继续研究