一. 链表2 两个整数相加—链表形式返回

你有两个用链表代表的整数,其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序,使得第一个数字位于链表的开头。写出一个函数将两个整数相加,用链表形式返回和。

思路:先将链表转化为数字,将其进行加减,然后将结果转化为链表。

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位)时,两个链表相加就得不到结果。

所以,我想:

  1. python真好,不用考虑变量类型。
  2. 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;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,053评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,527评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,779评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,685评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,699评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,609评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,989评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,654评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,890评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,634评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,716评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,394评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,976评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,950评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,191评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,849评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,458评论 2 342

推荐阅读更多精彩内容