LeetCode-两数相加

在代码的世界中有一句名言，即程序=数据结构+算法。工作中大部分开发其实都用不到多高深的算法，因为前辈们已经造好了各种高级轮子，我们要做的仅仅只需要调用他们封装好的API就行了。这样就算不懂这些知识，只要Java API、开发框架用得熟练，照样可以把代码写得“飞”起来。但语言只是工具，而算法才是灵魂。而程序就等于算法加数据结构。足以可见，想要在编程之路上走的更长远，数据结构与算法就是必须要掌握的基本功。在看一些中间件的源码时，越发感觉如此。不然就算开发了五年八年，也只是个coder，而不能称为工程师。接下来一段时间我会有选择的刷一些LeetCode算法题，提高内功吧。我会尽量使用 Java，Python和Go 三种语言实现算法

两数相加

原题题干如下：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解题思路

这个算法题难度在LeetCode上是中等难度，不知道这个难度是怎么定义的，就这道题而言。我大概看完题目想了一分钟的样子想到解题思路（PS：力扣上很多题，我看完题目，完全没有解题思路，无从下手的感觉，o(>_<)o ~）。只需把两个链表对应位置的数字相加就可以了，按这个思路这道题需要解决的问题点有三个

1. 同步遍历：所谓同步遍历，就是说同时开始遍历且步长一样，通俗的讲就是链表1遍历到第一个元素时，链表2也遍历到第一个元素，链表1遍历到第二个元素时，链表2也遍历到第二个元素。
2. 加法进位：在两个数字相加时可能需要进位，因此要额外声明一个变量用来记录上一次的结果是否需要进位
3. 空位补零：题干中给的示例两个链表是等长的，如果两个链表不等长该怎么处理，例如 342+7465 。这里我想到是补零，即转化为 0342+7465，这样虽然多了一次运算但是 0+7还是等于7，代码实现更加简洁

大概就是这样吧，具体写代码实现时，还有些细节需要考虑，例如两个链表等长，当两个链表都遍历完，但最后一次运算需要进位时，还要额外做一下处理。话不多说，上代码吧

代码实现

Java版本

ListNode.class

public class ListNode {

    private int value;
    private ListNode next;

    public ListNode(int value){
        this.value=value;
    }

    public ListNode(int value,ListNode next){
        this.value=value;
        this.next=next;
    }

    public int getValue() {return value;}

    public void setValue(int value) {this.value = value;}

    public ListNode getNext() {return next;}

    public void setNext(ListNode next) {this.next = next;}
}

测试类

package com.example.test;


/**
 * @Auther: Lushunjian
 * @Date: 2019/1/6 15:52
 * @Description:
 */
public class Test {

    public static void main(String[] args){
        ListNode num1 = new ListNode(2,new ListNode(4,new ListNode(3,null)));
        ListNode num2 = new ListNode(5,new ListNode(6,new ListNode(4,null)));
        ListNode data = addTwoNumbers(num1,num2);
        while (data != null){
            System.out.println(data.getValue());
            data = data.getNext();
        }

    }

    public static ListNode addTwoNumbers(ListNode num1 ,ListNode num2){
        // 进位标记  为true表示本次计算需要进位
        boolean carry = false;
        ListNode rootNode = new ListNode(-1);
        ListNode preNode = rootNode;
        // 当两个链表任意一个next还存在时，或者两个链表next都不存在，但上一次的计算结果需要进位时，都要继续循环
        while (num1 != null || num2 != null || carry){
            // 空位补零，
            int value1= num1 == null ? 0 : num1.getValue();
            int value2= num2 == null ? 0 : num2.getValue();
            // 计算本次结果
            // 如果上一次的计算需要进位，则+1
            int res = carry ? (value1+value2+1) : (value1+value2);
            carry = res >= 10;
            ListNode node = new ListNode(res%10);
            preNode.setNext(node);
            // 保存上一个节点
            preNode = node;
            if(num1 != null)
                num1 = num1.getNext();
            if(num2 != null)
                num2 = num2.getNext();
        }
        return rootNode.getNext();
    }
}

Python版本

ListNode.py

class ListNode(object):
    def __init__(self,val,next):
        self.val=val
        self.next=next

def addTwoNumbers(num1 : ListNode,num2 : ListNode) -> ListNode:
    rootNode = ListNode(-1,None)
    preNode = rootNode;
    carry = 0;
    while num1 or num2 or carry:
        value1 = num1.val if num1 else 0
        value2 = num2.val if num2 else 0
        res = value1+value2+1 if carry else value1+value2
        carry = res>=10
        node = ListNode(res%10,None)
        preNode.next = node
        preNode = node
        num1 = num1.next if num1 else None
        num2 = num2.next if num2 else None
    return rootNode.next

测试类

from study.ListNode import ListNode,addTwoNumbers

if __name__ == '__main__':
    num1 = ListNode(2,ListNode(4,ListNode(3,None)))
    num2 = ListNode(5,ListNode(6,ListNode(4,None)))
    data = addTwoNumbers(num1, num2)
    while data:
        print(data.val)
        data = data.next

Go版本

package main

type ListNode struct {
    value int
    next * ListNode
}


func addTwoNumbers2(num1 *ListNode ,num2 *ListNode) *ListNode{
    var carry bool
    carry = false
    var rootNode = &ListNode{ value: -1}
    var preNode = rootNode
    for num1 != nil || num2 != nil || carry {
        var value1 = 0
        var value2 = 0
        if num1 != nil{
            value1 = num1.value
        }
        if num2 != nil{
            value2 = num2.value
        }
        var res = 0
        if carry {
            res = value1+value2+1
        }else {
            res = value1+value2
        }

        if res>=10 {
            carry = true
        }else {
            carry = false
        }

        var node = &ListNode{ value: res%10}
        preNode.next = node
        preNode = node
        if num1 != nil{
            num1 = num1.next
        }
        if num2 != nil{
            num2 = num2.next
        }
    }
    return rootNode.next
}

func main()  {
    // 2->4->3
    var num1 = createNode(2)
    var num12 = createNode(4)
    num12.setNextNode(createNode(3))
    num1.setNextNode(num12)

    // 5->6->4
    var num2 = createNode(5)
    var num22 = createNode(6)
    num22.setNextNode(createNode(4))
    num2.setNextNode(num22)

    var data = addTwoNumbers2(num1,num2)
    for data != nil {
        println(data.value)
        data = data.next
    }
}

总结

嗯…感觉良好，继续加油吧。下面贴一下LeetCode的提交结果，令我惊讶的是，Java短短10多行的代码竟然占用40M的运行内存。但运行时间仅用了2毫秒。而Go语言内存只占用了5M，果然性能很高。