首页 > 试题广场 >

链式A+B

[编程题]链式A+B
  • 热度指数:43348 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

将两个反向存储在链表中的整数求和(即整数的个位存放在了链表首部,一位数对应一个节点),返回的结果仍用链表形式。

给定两个链表ListNode* A,ListNode* B,请返回A+B的结果(ListNode*)。

测试样例:
{1,2,3},{3,2,1}
返回:{4,4,4}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
推荐
思路

本题的思路很简单,按照小学数学中学习的加法原理从末尾到首位,对每一位对齐相加即可。技巧在于如何处理不同长度的数字,以及进位和最高位的判断。这里对于不同长度的数字,我们通过将较短的数字补0来保证每一位都能相加。

代码
class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {
        // 头结点
        ListNode *head = new ListNode(-1);
        ListNode *p = head;
        ListNode *node = nullptr;
        int c = 0,sum,val1,val2;
        ListNode *pa = a,*pb = b;
        //加法
        while(pa != nullptr || pb != nullptr || c != 0){
            val1 = (pa == nullptr ? 0 : pa->val);
            val2 = (pb == nullptr ? 0 : pb->val);
            sum = val1 + val2 + c;
            // 进位
            c = sum / 10;
            node = new ListNode(sum % 10);

            //尾插法
            p->next = node;
            p = node;
            pa = (pa == nullptr ? nullptr : pa->next);
            pb = (pb == nullptr ? nullptr : pb->next);
        }//while
        return head->next;
    }
};

编辑于 2015-09-28 18:59:13 回复(5)
	public static ListNode plusAB(ListNode a, ListNode b) {
		// write code here
		ListNode resultHead = new ListNode(-1);
		ListNode resultCurrent = resultHead;
		int addToNextDigit = 0;
		while (a != null || b != null || addToNextDigit != 0) {
			int aVal = a != null ? a.val : 0;
			int bVal = b != null ? b.val : 0;

			int sum = aVal + bVal + addToNextDigit;
			int nodeDigit = sum % 10;
			addToNextDigit = sum / 10;

			resultCurrent.next = new ListNode(nodeDigit);
			resultCurrent = resultCurrent.next;

			a = a != null ? a.next : null;
			b = b != null ? b.next : null;
		}
		return resultHead.next;
	}

发表于 2015-07-15 17:01:20 回复(25)
Ron头像 Ron

/*可以用此法完成大数加减,乘法也可以(加减乘都是从低位到高位)
除法需要从高位开始到低位*/ 
public class Plus {
	public ListNode plusAB(ListNode a, ListNode b) {
		// write code here
		if(a == null || b == null){
			return null;
		}
		int add = 0;
		ListNode head = new ListNode(-1);
		ListNode resCur = head;
		ListNode curA = a;
		ListNode curB = b;
		while(curA != null || curB != null){
			if(curA != null && curB !=null){
				resCur.next = new ListNode((curA.val+curB.val+add)%10);
				resCur = resCur.next;
				add = (curA.val+curB.val+add)/10;
				curA = curA.next;
				curB = curB.next;
			}else if(curA != null){
				resCur.next = new ListNode((curA.val+add)%10);
				resCur = resCur.next;
				add = (curA.val+add)/10;
				curA = curA.next;
			}else{
				resCur.next = new ListNode((curB.val+add)%10);
				resCur = resCur.next;
				add = (curB.val+add)/10;
				curB = curB.next;
			}
		}
        if(add > 0){
			resCur.next = new ListNode(add);
			resCur = resCur.next;
		}
		return head.next;
	}
}

编辑于 2015-08-31 16:47:44 回复(4)

python 解法.

思路很简单,我这种解法根本不用考虑进位和补位这种麻烦问题。

1、先把a和b表示的整数取出来

2.再计算两个数的和

3.把和表示为链表。


class Plus:
    def plusAB(self, aHead, bHead):
        # resA 和resB中放a和b的所有数字
        resA, resB = [], []
        while aHead:
            resA.append(str(aHead.val))
            aHead = aHead.next
        while bHead:
            resB.append(str(bHead.val))
            bHead = bHead.next

        # 计算a+b的和
        result = str(int("".join(resA[::-1])) + int("".join(resB[::-1])))

        #创建一个链表,从个位开始存放。
        dummy = ListNode(0)
        pre = dummy
        for i in result[::-1]:
            node = ListNode(int(i))
            pre.next = node
            pre = pre.next
        return dummy.next
编辑于 2017-10-16 11:46:31 回复(1)
public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        ListNode p1 = a, p2 = b;
        ListNode head = new ListNode(0);
        ListNode p = head;
        int sum = 0;
        while (p1 != null || p2 != null || sum != 0) {
            if (p1 != null) {
                sum += p1.val;
                p1 = p1.next;
            }
            if (p2 != null) {
                sum += p2.val;
                p2 = p2.next;
            }
            p.next = new ListNode(sum % 10);
            sum /= 10;
            p = p.next;
        }
        return head.next;
    }
}

发表于 2016-09-02 16:43:25 回复(3)
//思路:相加后,结果都放在b中,如果链表a长,则把a剩余的部分连接在b后
class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {
        // write code here
        if(a==NULL||b==NULL)
            return NULL;
        ListNode *head=b;//相加后的结果存放在链表b
		int temp=0;//进位标志
		int sum=0;//加的和
    	while(a->next!=NULL&&b->next!=NULL){
    		//之前这样写 是错误的(检查了好久)
//    		b->val=(a->val+b->val+temp)%10;
//    		temp=(a->val+b->val+temp)/10;
    		sum=a->val+b->val+temp;
    		b->val=sum%10;
    		temp=sum/10;
    		a=a->next;
    		b=b->next;
    	}
    	if(a->next==NULL&&b->next==NULL){//链表等长
    		sum=a->val+b->val+temp;
    		b->val=sum%10;
    		temp=sum/10;
    		if(temp>0){
    			ListNode* newnode=new ListNode(temp);
    			b->next=newnode;
    		}
    		return head;
    	}
    	if(a->next==NULL&&b->next!=NULL){//链表b较长
    		sum=a->val+b->val+temp;
    		b->val=sum%10;
    		temp=sum/10;
    		b->next->val+=temp;
    		return head;
    	}
    	if(a->next!=NULL&&b->next==NULL){//链表a较长
    		sum=a->val+b->val+temp;
    		b->val=sum%10;
    		temp=sum/10;
    		a->next->val+=temp;
    		b->next=a->next;
    		return head;
    	}
    }
};

发表于 2015-11-13 15:42:50 回复(2)
用递归的方式时间和空间复杂度更小:
public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        return plusAB(a, b, 0);
    }
    
    private ListNode plusAB(ListNode a, ListNode b, int sum) {
        if (a == null && b == null && sum == 0) {
            return null;
        }
        if (a != null) {
            sum += a.val;
        }
        if (b != null) {
            sum += b.val;
        }
        ListNode node = new ListNode(sum % 10);
        node.next = plusAB(a != null ? a.next : null, b != null ? b.next : null, sum / 10);
        return node;
    }
}

发表于 2017-06-08 10:49:59 回复(3)
//O(n)算法,解析看注释吧
 public ListNode plusAB(ListNode a, ListNode b) {
        if(a==null||b==null) return null;
        ListNode cur=a;
        int temp=0;
        while(cur!=null){
            if(b==null) break;//b链表结束,咱就退出
            temp+=cur.val+b.val;//当前位累加
            cur.val=temp%10;//a链表存储和
            temp=temp/10;//取进位
            if(cur.next==null&&b.next!=null) cur.next=new ListNode(0);//a长度没b长就增加长度
            if(cur.next==null&&b.next==null&&temp!=0) cur.next=new ListNode(temp);//加到末尾,如果有进位,就增加进位节点
            cur=cur.next;
            b=b.next;
        }
        return a;
    }

编辑于 2017-05-11 22:11:38 回复(8)
思路很简单也很清晰, 两结点值跟进位相加,满10进位1。
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Plus:
    def plusAB(self, a, b):
        if not a: return b
        if not b: return a
        
        carry = 0
        head = p = ListNode(-1)
        
        while a and b:
            node = ListNode((a.val + b.val + carry)%10)
            p.next = node
            carry = 1 if (a.val + b.val + carry) >= 10 else 0 
            a, b, p = a.next, b.next, p.next
            
        tmp = a if a else None
        tmp = b if b else tmp
        # 是否还有链表未迭代完
        while tmp:
            node = ListNode((tmp.val + carry)%10)
            p.next = node
            carry = 1 if (tmp.val + carry >= 10) else 0
            p, tmp = p.next, tmp.next
        # 是否还有进位
        if carry:
            node = ListNode(1)
            p.next = node
            p = p.next
       	p.next = None
        return head.next

发表于 2016-08-02 09:24:34 回复(0)
//详细注释,喜欢的点点赞呀
public static ListNode plusAB(ListNode a, ListNode b) {
        ListNode result=new ListNode(-1);//为了等会尾插方便,事先建立一个头结点,用来保存结果的链表
        ListNode newHead=result;//为了输出时方便输出(提前用一个节点记录头结点)
        int c=0,val1,val2,sum; //c是每一位数字除以10的结果,val1是链表a的节点的值,val2是链表b的节点的值
        while(a!=null||b!=null||c!=0){//这里加入c!=0是为了防止加最后一位数时恰好到了10,然后输出的时候不让它漏掉1
            //这里的三目表达式是为了防止有一个链表比较短,如果有一个先遍历完了之后后边的位置用0代替直到另一个也遍历完
             val1=(a==null?0:a.val);
             val2=(b==null?0:b.val);
             sum=val1+val2+c; //准备进行进位操作
             c=sum/10;
             ListNode node=new ListNode(sum%10);
//大于10把大于10的那部分放进去,小于等于10把本来的和放进去
             result.next=node;              result=result.next; //result向后移动一位              a=(a==null?null:a.next); //这里是为了防止a==null,然后造成空指针异常              b=(b==null?null:b.next); //同上         }         return newHead.next;//返回事先记录好的节点,跳过那个自己建立的第一个节点输出     }

编辑于 2019-12-04 19:32:25 回复(0)
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        // write code here
        ListNode cc = new ListNode(0);
        ListNode c = cc;
        int flag = 0;
        int val = 0;
        int va = 1;
        int sum = 0;
        int ccc = 0;
        while(a != null || b != null || ccc != 0){
            val = (a == null ? 0 : a.val);
            va = (b == null ? 0 : b.val);
            sum  = val + va + ccc;
            flag = sum % 10;
            ccc = sum / 10;
            c.next = new ListNode(flag);
            c = c.next;
            a = (a == null ? null : a.next);
            b = (b == null ? null : b.next);
        }
        c.next = null;
        return cc.next;
    }
}

发表于 2018-08-28 17:39:21 回复(0)
L0L头像 L0L
ListNode* plusAB(ListNode* a, ListNode* b) {
			int carry=0;
			ListNode *retHead=new ListNode(0);
			ListNode *p=retHead;
			while(a||b||carry) {
				int vala=a?a->val:0;
				int valb=b?b->val:0;
				int val=(vala+valb+carry)%10;
				carry=(vala+valb+carry)/10;
				ListNode *tmp=new ListNode(val);
				p->next=tmp;
				p=p->next;
				a=a?a->next:NULL;
				b=b?b->next:NULL;
			}
			p->next=NULL;
			return retHead->next;
		}

发表于 2015-10-02 11:09:19 回复(1)
public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        // write code here
        if (a == null) return b;
        if (b == null) return a;
        ListNode pA = a;
        ListNode pB = b;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        
        int carry = 0;
        while (pA != null && pB != null) {
            int sum = pA.val + pB.val + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            pA = pA.next;
            pB = pB.next;
        }
        while (pA != null) {
            int sum = pA.val + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            pA = pA.next;
        }
        while (pB != null) {
            int sum = pB.val + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            pB = pB.next;
        }
        if (pA == null && pB == null && carry != 0) {
            cur.next = new ListNode(carry);
        }
        return dummy.next;
    }
}

发表于 2019-11-26 09:19:55 回复(0)
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {
        ListNode* head =new ListNode(0);
         ListNode* cur = head;
        int plus = 0;
        while(a||b)
        {
            int num = (a?a->val:0)+(b?b->val:0)+plus;
            if(num >= 10)
            {
                num -= 10;
                plus =1;
            }
            else
                plus = 0;
            cur->next =new ListNode(num);
            cur = cur->next;
            if(a)
                a =a->next;
            if(b)
                b=b->next;
        }
        if(plus)
            cur->next =new ListNode(plus);
        return head->next;
    }
};
发表于 2018-01-21 11:36:42 回复(0)
总结这题的收获,我注释的都是编译不通过的,节点指针赋初值的时候,不要用NULL,
用new (0)更好,同时指针不要简单的用p=p->next,可能会出现各种意外,
反正编译就是不通过。同时也希望大神抽空花点您宝贵的时间,可以给我解释解释

class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {
        // 头结点
        ListNode *head =new ListNode(0);//ListNode *head=NULL;
        ListNode *p = head;
        int mod= 0,sum,x,y;
        ListNode *pa = a,*pb = b;
        while(pa !=NULL || pb != NULL || mod != 0){
            x = (pa == NULL ? 0 : pa->val);
            y= (pb == NULL ? 0 : pb->val);
            sum = x + y + mod;
            mod = sum / 10;
            p->next = new ListNode(sum % 10);
           p=p->next;
            pa = (pa == NULL ? NULL : pa->next);//pa=pa->next;
            pb = (pb == NULL ? NULL: pb->next);//pb=pb->next;
        }
        return head->next;
    }
};

编辑于 2017-08-30 10:51:45 回复(0)
class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) {
        if(!a || !b) return a?a:b;
        ListNode* res=a,*apre;
        int jin=0;
        while(a && b){
            int temp=a->val + b->val + jin;
            a->val = temp%10;
            jin = temp/10;
            if(!a->next) apre=a;
            a=a->next;  b=b->next;
        }
        if(b) apre->next=b;
        if(!a) a=b;
        while(a){
            int temp = a->val + jin;
            a->val = temp%10;
            jin=temp/10;
            if(!a->next) apre=a;
            a=a->next;
        }
        if(jin) apre->next = new ListNode(jin);
        return res;
    }
};
发表于 2017-08-17 21:58:52 回复(0)
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Plus {
public:
    ListNode* plusAB(ListNode* a, ListNode* b) 
    {
        if(!a) return b;
        if(!b) return a;
        ListNode *L1 = new ListNode(0),*L2 = new ListNode(0);
        L1->next = a,L2->next = b;
        auto prep = L1,preq = L2,p = a,q = b;
        int carry = 0;
        while(p && q)
        {
            int sum = p->val + q->val + carry;
            if(sum >= 10){sum -= 10;carry = 1;}
            else carry = 0;
            p->val = sum;
            prep = p;
            preq = q;
            p = p->next;
            q = q->next;
        }
        if(!p) {prep->next = q;p = q;}
        while(p && carry + p->val == 10)
        {
            p->val = 0;
            prep = p;
            p = p->next;
        }
        if(!p && carry == 1)
        {
            ListNode* temp = new ListNode(1);
            prep->next = temp;
        }
        else if(p && carry == 1)
            ++p->val;
        
        return L1->next;
    }
};

发表于 2017-06-29 15:36:44 回复(0)
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        return addListsHelper(a, b, 0);
    }
    
    public ListNode addListsHelper(ListNode a, ListNode b, int carry) {
        if (a == null && b == null && carry == 0) {
            return null;
        }
        int data = carry;
        if (a != null) {
            data += a.val;
        }
        if (b != null) {
            data += b.val;
        }
        ListNode node = new ListNode(data % 10);
        node.next = addListsHelper(a == null ? null : a.next,
                          b == null ? null : b.next,
                          data >= 10 ? 1 : 0);
        return node;
    }
}

发表于 2017-06-20 15:39:26 回复(0)
import java.util.*;
//自己太菜了,模仿别人做出来的,判断null很重要

public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        ListNode head =new ListNode(-1);
        ListNode p =head;
        if(a ==null){
            return b;
        }
        if(b ==null){
            return a;
        }
        int num =0;
        while(a!=null||b!=null||num !=0){
            int aval = a==null ? 0:a.val;
            int	bval = b==null ? 0:b.val;
            int cval = aval+bval+num;
            int sum =cval%10;
            num =cval/10;
            p.next =new ListNode(sum); 
            p=p.next;
            a=a ==null?null:a.next;
            b=b==null?null:b.next;
        }
        return head.next;
        
        
    }
}

发表于 2017-05-16 23:55:15 回复(0)
//Java version for this question
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null; ListNode(int val) {
        this.val = val;
    }
}*/
public class Plus {
    public ListNode plusAB(ListNode a, ListNode b) {
        ListNode p = new ListNode(-1);
        ListNode pHead = p;
        ListNode pNode = null;
        int sum = 0, c = 0, valA, valB;
        ListNode paNode = a, pbNode = b;
        while(paNode != null || pbNode != null || c != 0){
            valA = (paNode == null ? 0 : paNode.val);
            valB = (pbNode == null ? 0 : pbNode.val);
            sum = valA + valB + c;
            c = sum / 10;
            pNode = new ListNode(sum % 10);
            
            p.next = pNode;
            p = p.next;
            paNode = (paNode == null ? null : paNode.next);
            pbNode = (pbNode == null ? null : pbNode.next);            
        }
        p.next = null;
        return pHead.next;
    }
}

编辑于 2017-05-01 11:47:16 回复(2)
/*@1.两个数位数一样多(每一位都面临进位)
//@2.两数位数不一样多(A数比B数多出来的几位,
是不面临进位的,而对 等的位数都面临进位)*/
public class Plus { //首先定义全局头指针和位指针 ListNode head=null; ListNode tail=null; public ListNode plusAB(ListNode a, ListNode b) { // write code here //首先定义需要的变量 //进位标志 int flag=0; //首先分析两数长度一样的情况 while(a!=null&&b!=null){ insert((a.val+b.val+flag)%10); //将进位进行标记 flag=(a.val+b.val+flag)/10; a=a.next; b=b.next; } //如果A B两数同长,但最后发生了进位,则把进位装入新的一位,否则继续把进位加入下面情况 if(a==null&&b==null&flag!=0){ insert(flag); } //两数长度不一样的情况 if(a==null&&b!=null){ while(b!=null){ insert(b.val+flag); flag=(b.val+flag)/10; b=b.next; } } if(b==null&&a!=null){ while(a!=null){ insert(a.val+flag); flag=(a.val+flag)/10; a=a.next; } } return head; } public void insert(int result){ //首先创建一个新节点 ListNode node=new ListNode(result); if(head==null){ head=node; tail=node; }else{ tail.next=node; tail=node; } }

编辑于 2017-04-11 11:03:22 回复(0)