破解编程面试---链接的加法（八种编程语言的实现）

破解编程面试---链接的加法（八种编程语言的实现）

我们有两个非空链表，它们代表两个非负整数。这些数字以相反的顺序存储，并且它们的每个节点都包含一个数字。将两个数字相加，然后将它们作为链接列表返回。

您可能会假设两个数字除了数字0本身以外都不包含任何前导零。

例：

输入：（2-> 4-> 3）+（5-> 6-> 4）

输出：7-> 0-> 8

说明：342 + 465 = 807。

思路：

链表节点数据结构中包含值和下一个节点。

两个链表相加要对每个对应元素进行加操作；

如果计算结果超过了10，需要移位到高位；

如果有链表为空了，需要用最后的移位值0或者1对单独的链表中剩余的元素进行加操作；

最后再检查移位值，如果不为零，则添加为新元素。

Javascript:

class ListNode {

constructor(val, next=null) {

this.val = val;

}

addTwoNumbers = (l1, l2)=> {

let newNode = null;

let head = null;

let overTen = 0;

while(l1 != null && l2 != null) {

let sum = l1.val + l2.val + overTen;

let v1 = sum % 10;

overTen = parseInt(sum / 10);

if (head == null) {

head = new ListNode(v1);

newNode = head;

}

else {

newNode.next = new ListNode(v1);

newNode = newNode.next;

}

l1 = l1.next;

l2 = l2.next;

}

let l = !l1? l2 : l1;

while(l) {

let sum = l.val + overTen;

let v1 = sum % 10;

overTen = parseInt(sum / 10);

newNode.next = new ListNode(v1);

newNode = newNode.next;

l = l.next;

}

if(overTen != 0) {

newNode.next = new ListNode(overTen);

}

return head;

};

{

let l1 = new ListNode(2);

l1.next = new ListNode(4);

l1.next.next = new ListNode(3);

let l2 = new ListNode(5);

l2.next = new ListNode(6);

l2.next.next = new ListNode(4);

let l = addTwoNumbers(l1, l2);

while(l != null) {

console.log(l.val);

l = l.next;

}

console.log();

}

{

let l1 = new ListNode(1);

l1.next = new ListNode(8);

let l2 = new ListNode(0);

let l = addTwoNumbers(l1, l2);

while(l != null) {

console.log(l.val);

l = l.next;

}

console.log();

}

Java:

import java.util.*;

public class HelloWorld{

static class ListNode {

int val;

ListNode next;

ListNode(int x) { val = x; }

}

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode newNode = null;

ListNode head = null;

int overTen = 0;

while(l1 != null && l2 != null){

int sum = l1.val + l2.val + overTen;

int v1 = sum % 10;

overTen = sum / 10;

if(head == null){

head = new ListNode(v1);

newNode = head;

}

else{

newNode.next = new ListNode(v1);

newNode = newNode.next;

}

l1 = l1.next;

l2 = l2.next;

}

ListNode l = l1 == null? l2: l1;

while(l != null){

int sum = l.val + overTen;

int v1 = sum % 10;

overTen = sum / 10;

newNode.next = new ListNode(v1);

newNode = newNode.next;

l = l.next;

}

if(overTen != 0){

newNode.next = new ListNode(overTen);

}

return head;

}

public static void main(String []args){

{

ListNode l1 = new ListNode(2);

l1.next = new ListNode(4);

l1.next.next = new ListNode(3);

ListNode l2 = new ListNode(5);

l2.next = new ListNode(6);

l2.next.next = new ListNode(4);

ListNode l = addTwoNumbers(l1, l2);

while(l != null) {

System.out.print(l.val);

l = l.next;

}

System.out.println();

}

{

ListNode l1 = new ListNode(1);

l1.next = new ListNode(8);

ListNode l2 = new ListNode(0);

ListNode l = addTwoNumbers(l1, l2);

while(l != null) {

System.out.print(l.val);

l = l.next;

}

System.out.println();

}

C#:

using System;

class ListNode {

public int val;

public ListNode next;

public ListNode(int x) { val = x; }

}

class HelloWorld {

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode newNode = null;

ListNode head = null;

int overTen = 0;

while(l1 != null && l2 != null){

int sum = l1.val + l2.val + overTen;

int v1 = sum % 10;

overTen = sum / 10;

if(head == null){

head = new ListNode(v1);

newNode = head;

}

else{

newNode.next = new ListNode(v1);

newNode = newNode.next;

}

l1 = l1.next;

l2 = l2.next;

}

ListNode l = l1 == null? l2: l1;

while(l != null){

int sum = l.val + overTen;

int v1 = sum % 10;

overTen = sum / 10;

newNode.next = new ListNode(v1);

newNode = newNode.next;

l = l.next;

}

if(overTen != 0){

newNode.next = new ListNode(overTen);

}

return head;

}

static void Main() {

Console.WriteLine("Hello World");

{

ListNode l1 = new ListNode(2);

l1.next = new ListNode(4);

l1.next.next = new ListNode(3);

ListNode l2 = new ListNode(5);

l2.next = new ListNode(6);

l2.next.next = new ListNode(4);

ListNode l = addTwoNumbers(l1, l2);

while(l != null) {

Console.Write(l.val);

l = l.next;

}

Console.WriteLine();

}

{

ListNode l1 = new ListNode(1);

l1.next = new ListNode(8);

ListNode l2 = new ListNode(0);

ListNode l = addTwoNumbers(l1, l2);

while(l != null) {

Console.Write(l.val);

l = l.next;

}

Console.WriteLine();

}

Swift:

import Foundation

public class ListNode {

public var val: Int

public var next: ListNode?

public init(_ val: Int) {

self.val = val

self.next = nil

}

func addTwoNumbers(_ la: ListNode?, _ lb: ListNode?) -> ListNode? {

var l1 = la

var l2 = lb

var newNode: ListNode?

var head: ListNode?

var overTen: Int = 0

while (l1 != nil && l2 != nil) {

var sum: Int = l1!.val + l2!.val + overTen

var v1 = sum % 10

overTen = sum / 10

if( head == nil) {

head = ListNode(v1)

newNode = head;

}

else {

newNode!.next = ListNode(v1)

newNode = newNode!.next

}

l1 = l1!.next

l2 = l2!.next

}

var l: ListNode? = l1 == nil ? l2 : l1

while (l != nil) {

var sum = l!.val + overTen

var v1 = sum % 10;

overTen = sum / 10;

newNode!.next = ListNode(v1);

newNode = newNode!.next;

l = l!.next;

}

if(overTen != 0) {

newNode!.next = ListNode(overTen)

}

return head

}

func test1() {

var l1: ListNode? = ListNode(2)

l1!.next = ListNode(4)

l1!.next!.next = ListNode(3)

var l2: ListNode? = ListNode(5)

l2!.next = ListNode(6)

l2!.next!.next = ListNode(4)

var l = addTwoNumbers(l1, l2)

while(l != nil) {

print("\(l!.val)", terminator:"")

l = l!.next

}

print("\n")

}

func test2() {

var l1: ListNode? = ListNode(1)

l1!.next = ListNode(8)

var l2: ListNode? = ListNode(0)

var l = addTwoNumbers(l1, l2)

while(l != nil) {

print("\(l!.val)", terminator:"")

l = l!.next

}

print("\n")

}

test1()

test2()

Kotlin:

import kotlin.properties.Delegates

class ListNode {

var `val`: Int = 0

var next: ListNode? = null

constructor(v: Int) {

this.`val` = v

}

fun addTwoNumbers(la: ListNode?, lb: ListNode?): ListNode? {

var l1: ListNode? = la

var l2: ListNode? = lb

var newNode: ListNode? = null

var head: ListNode? = null

var overTen: Int = 0

while (l1 != null && l2 != null) {

var sum: Int = l1?.`val` + l2?.`val` + overTen

var v1 = sum % 10

overTen = sum / 10

if (head == null) {

head = ListNode(v1)

newNode = head;

} else {

newNode?.next = ListNode(v1)

newNode = newNode?.next

}

l1 = l1?.next

l2 = l2?.next

}

var l: ListNode? = l1

if (l1 == null) {

l = l2

}

while (l != null) {

var sum = l?.`val` + overTen

var v1 = sum % 10;

overTen = sum / 10;

newNode?.next = ListNode(v1);

newNode = newNode?.next;

l = l?.next;

}

if (overTen != 0) {

newNode?.next = ListNode(overTen)

}

return head

}

fun main() {

test1()

test2()

}

private fun test1() {

var l1: ListNode? = ListNode(2)

l1?.next = ListNode(4)

l1?.next?.next = ListNode(3)

var l2: ListNode? = ListNode(5)

l2?.next = ListNode(6)

l2?.next?.next = ListNode(4)

var l = addTwoNumbers(l1, l2)

while (l != null) {

print("${l.`val`}")

l = l?.next

}

println()

}

private fun test2() {

var l1: ListNode? = ListNode(1)

l1?.next = ListNode(8)

var l2: ListNode? = ListNode(0)

var l = addTwoNumbers(l1, l2)

while (l != null) {

print("${l.`val`}")

l = l?.next

}

println()

}

Python:

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:

newNode = None

head = None

overTen = 0

while l1 != None and l2 != None:

sum = l1.val + l2.val + overTen

v1 = sum % 10

overTen = int(sum / 10)

if head == None:

head = ListNode(v1)

newNode = head

else:

newNode.next = ListNode(v1);

newNode = newNode.next

l1 = l1.next

l2 = l2.next

l = l1 if l1 != None else l2

while l != None:

v1 = l.val

if overTen != 0:

sum = l.val + overTen

v1 = sum % 10

overTen = int(sum / 10)

newNode.next = ListNode(v1);

newNode = newNode.next

l = l.next

if overTen != 0:

newNode.next = ListNode(overTen);

return head

def test1():

l1 = ListNode(2)

l1.next = ListNode(4)

l1.next.next = ListNode(3)

l2 = ListNode(5)

l2.next = ListNode(6)

l2.next.next = ListNode(4)

l = addTwoNumbers(l1, l2)

while l != None:

print(l.val, end = '')

l = l.next

print()

def test2():

l1 = ListNode(1)

l1.next = ListNode(8)

l2 = ListNode(0)

l = addTwoNumbers(l1, l2)

while l != None:

print(l.val, end = '')

l = l.next

print()

test1()

test2()

C++:

#include <stdio.h>

#include <iostream>

struct ListNode {

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode *newNode = 0;

ListNode *head = 0;

int overTen = 0;

while(l1 != 0 && l2 != 0) {

int sum = l1->val + l2->val + overTen;

int v1 = sum % 10;

overTen = sum /10;

if(head == 0){

head = new ListNode(v1);

newNode = head;

}

else {

newNode->next = new ListNode(v1);

newNode = newNode->next;

}

delete l1;

delete l2;

l1 = l1->next;

l2 = l2->next;

}

ListNode* l = l1 != NULL ? l1: l2;

while(l != NULL) {

int v1 = l->val;

if(overTen != 0){

int sum = l->val + overTen;

v1 = sum % 10;

overTen = sum / 10;

}

newNode->next = new ListNode(v1);

newNode = newNode->next;

delete l;

l = l->next;

}

if(overTen != 0) {

newNode->next = new ListNode(overTen);

}

return head;

}

void test1 () {

ListNode *l1 = new ListNode(2);

l1->next = new ListNode(4);

l1->next->next = new ListNode(3);

ListNode *l2 = new ListNode(5);

l2->next = new ListNode(6);

l2->next->next = new ListNode(4);

ListNode *l = addTwoNumbers(l1, l2);

while(l != NULL) {

std::cout << l->val;

delete l;

l = l->next;

}

std::cout << std::endl;

}

void test2 () {

ListNode *l1 = new ListNode(1);

l1->next = new ListNode(8);

ListNode *l2 = new ListNode(0);

ListNode *l = addTwoNumbers(l1, l2);

while(l != NULL) {

std::cout << l->val;

delete l;

l = l->next;

}

std::cout << std::endl;

}

int main()

{

test1();

test2();

return 0;

}

Golang:

package main

import (

"fmt"

)

type ListNode struct {

Val int

Next *ListNode

}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {

var newNode *ListNode = nil

var head *ListNode = nil

var overTen = 0

for l1 != nil && l2 != nil {

sum := l1.Val + l2.Val + overTen

v1 := sum % 10

overTen = sum /10

if head == nil {

head = &ListNode{Val: v1}

newNode = head

} else {

newNode.Next = &ListNode{Val: v1}

newNode = newNode.Next

}

l1 = l1.Next

l2 = l2.Next

}

l := l1

if l1 == nil {

l = l2

}

for l != nil {

v1 := l.Val;

if overTen != 0{

sum := l.Val + overTen

v1 = sum % 10

overTen = sum / 10

}

newNode.Next = &ListNode{Val: v1}

newNode = newNode.Next

l = l.Next

}

if overTen != 0 {

newNode.Next = &ListNode{Val: overTen }

}

return head

}

func test1() {

l1 := &ListNode {Val: 2}

l1.Next = &ListNode {Val: 4}

l1.Next.Next = &ListNode {Val: 3}

l2 := &ListNode {Val: 5}

l2.Next = &ListNode {Val: 6}

l2.Next.Next = &ListNode {Val: 4}

l := addTwoNumbers(l1, l2)

for l != nil {

fmt.Printf("%d", l.Val)

l = l.Next

}

fmt.Println();

}

func test2() {

l1 := &ListNode {Val: 1}

l1.Next = &ListNode {Val: 8}

l2 := &ListNode {Val: 0}

l := addTwoNumbers(l1, l2)

for l != nil {

fmt.Printf("%d", l.Val)

l = l.Next

}

fmt.Println();

}

func main() {

test1()

test2()

}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 199,711评论 5赞 468
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 83,932评论 2赞 376
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 146,770评论 0赞 330
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 53,799评论 1赞 271
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 62,697评论 5赞 359
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,069评论 1赞 276
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,535评论 3赞 390
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,200评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,353评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,290评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,331评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,020评论 3赞 315
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,610评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,694评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,927评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,330评论 2赞 346
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 41,904评论 2赞 341

破解编程面试---链接的加法 （八种编程语言的实现）

推荐阅读更多精彩内容

破解编程面试---链接的加法（八种编程语言的实现）