【题目描述】
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored inreverseorder, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
你有两个用链表代表的整数,其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序,使得第一个数字位于链表的开头。写出一个函数将两个整数相加,用链表形式返回和。
【题目链接】
www.lintcode.com/en/problem/add-two-numbers/
【题目解析】
本题要求将以链表存储的两个整数相加,求和的结果依然存储在一个链表中,最后返回结果链表的头指针。
题目的难点在于
1. 两个整数逆序存储,低位向高位有进位时不再是向前而是向后进位。
2. 两个整数不一定有相同的位数,所以遍历链表时要判断是否遍历结束,如果结束,就将其相应位置为0。
3. 两个整数的最高位相加可能产生进位。
综上考虑,应创建一个新的链表,其头节点为head,指向其的头指针为p,用carry表示对应位相加后的进位,sum表示相加后结果。
sum等于两个整数对应位相加再加上低位进位,sum向高位的进位carry = sum / 10,此时结果链表新增一个节点,其val = sum % 10即p->next = new ListNode(sum % 10)。这样便完成了一次加法和进位操作,结果链表和两个存储整数的链表的指针向后移动一位,重复之前的加法和进位操作,直到两个整数遍历结束且不存在进位。
【参考答案】