你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
思路：先将链表转化为数字，将其进行加减，然后将结果转化为链表。
Python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param l1: the first list
# @param l2: the second list
# @return: the sum list of l1 and l2
def addLists(self, l1, l2):
# write your code here
first_number = 0
second_number = 0
# 设计一个函数用来将list 转化为 number
def list_to_number(l):
x = 1
number = 0
while l != None:
number += l.val * x
x = 10 * x
if l.next != None:
l = l.next
else: break
return number
first_number = list_to_number(l1)
second_number = list_to_number(l2)
sum = first_number + second_number
sum1 = sum
number_of_node = 0
# 如果sum为0, 返回这个node（0，null）
if sum == 0:
node = ListNode(0)
node.next = None
return node
# 当sum > 0，计算这个sum有多少位的数字，就有多少个node
while sum > 0:
sum = sum - sum % 10**(number_of_node + 1)
number_of_node += 1
last_node = None
# 倒数每一个node（方便设置node.next的值）
while number_of_node !=0:
val = int(sum1 / (10**(number_of_node - 1)))
sum1 = sum1 - val* 10**(number_of_node - 1)
number_of_node -= 1
node = ListNode(val)
node.next = last_node
last_node = node
return last_node
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/
// 将链表转化为数字
public long list_to_number(ListNode list)
{
ListNode head = list;
long number = 0L;
int number_of_node = 0;
while(list != null)
{
list = list.next;
number_of_node += 1;
}
for (int index = 0; index <number_of_node; index++)
{
number += head.val* Math.pow(10,index);
head = head.next;
}
return number;
}
public ListNode addLists(ListNode l1, ListNode l2) {
long first_number;
long second_number;
// 记录sum有多少位数字
long integer = 1;
// 转化链表得到数字
first_number = list_to_number(l1);
second_number = list_to_number(l2);
// 计算两数的和
long sum = first_number + second_number;
if (sum == 0){
return l1;
}
while(sum - integer >= 0){
integer *= 10 ;
}
ListNode last_node = null;
// 将sum转化为链表
while(integer > 1){
// 得到每个node的值
int value;
value = (int)(sum / (integer / 10));
sum -= value*(integer /10);
integer /= 10;
// 新建一个node
ListNode node = new ListNode(value);
node.next = last_node;
last_node = node;
}
return last_node;
}
}
思路：以上code是基于python的思路，一开始我对数字使用int，但是当列表长度较大时，加法得到的sum就会超过int的范围（4个字节，32位，2147483647），于是我改用long，但是当sum超过9223372036854775807（8个字节，64位）时，两个链表相加就得不到结果。
所以，我想：
- python真好，不用考虑变量类型。
- java的思路需要改改，参考很多资料后，我有了新的思路，利用node的插入来解决问题。
Java 新思路
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/
public ListNode addLists(ListNode l1, ListNode l2) {
// set up 进位
int carry = 0;
// set up a node to store the last node
ListNode last_node = null;
// set up return value
ListNode head = null;
// when list 1 and list 2 are both nonempty
while (l1 !=null & l2 != null)
{
int value = l1.val + l2.val + carry;
l1 = l1.next;
l2 = l2.next;
carry = value / 10;
value = value % 10;
ListNode node = new ListNode(value);
// if this node is not the first node
if (last_node != null)
{
last_node.next = node;
last_node = node;
}
else
{
head = node; // give the first node to return value
last_node = node;
}
}
// when there is only one list empty.
while (l1 != null || l2 != null )
{
if (l1 != null)
{
int value = l1.val + carry;
l1 = l1.next;
carry = value / 10;
value = value % 10;
ListNode node = new ListNode(value);
last_node.next = node;
last_node = node;
}
else
{
int value = l2.val + carry;
l2 = l2.next;
carry = value / 10;
value = value % 10;
ListNode node = new ListNode(value);
last_node.next = node;
last_node = node;
}
}
// if there is a carry in the last addition
if (carry == 1 )
{
ListNode node = new ListNode(carry);
last_node.next = node;
}
return head;
}
}
