05/16 20:18

# 一、说明

给定两个 非空 链表来表示两个非负整数。位数按照 逆序 方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

# 二、解决方案参考

1. Swift 语言

class AddTwoNumbers {
func addTwoNumbers(l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var carry = 0, l1 = l1, l2 = l2
let dummy = ListNode(0)
var node = dummy

while l1 != nil || l2 != nil || carry != 0 {
if l1 != nil {
carry += l1!.val
l1 = l1!.next
}
if l2 != nil {
carry += l2!.val
l2 = l2!.next
}

node.next = ListNode(carry % 10)
node = node.next!

carry = carry / 10
}

return dummy.next
}
}

2. JavaScript 语言


/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/

var addTwoNumbers = function(l1, l2) {
, ans

while(l1 || l2) {
var a = l1 ? l1.val : 0
, b = l2 ? l2.val : 0;

var sum = a + b + add;

var node = new ListNode(sum % 10);

if (!ans)
else {
}

if (l1)
l1 = l1.next;
if (l2)
l2 = l2.next;
}

}

return ans;
};


3. Python 语言

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
# maybe standard version
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
p = dummy = ListNode(-1)
carry = 0
while l1 and l2:
p.next = ListNode(l1.val + l2.val + carry)
carry = p.next.val / 10
p.next.val %= 10
p = p.next
l1 = l1.next
l2 = l2.next

res = l1 or l2
while res:
p.next = ListNode(res.val + carry)
carry = p.next.val / 10
p.next.val %= 10
p = p.next
res = res.next
if carry:
p.next = ListNode(1)
return dummy.next

# shorter version
p = dummy = ListNode(-1)
carry = 0
while l1 or l2 or carry:
val = (l1 and l1.val or 0) + (l2 and l2.val or 0) + carry
carry = val / 10
p.next = ListNode(val % 10)
l1 = l1 and l1.next
l2 = l2 and l2.next
p = p.next
return dummy.next



4. Java 语言

public class ListNode {
public int val;
public ListNode next;

public ListNode(int i) {
this.val = i;
}

public int val() {
return val;
}
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
}


5. C++ 语言

class Solution {

public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
int x=0, y=0, carry=0, sum=0;
ListNode *h=NULL, **t=&h;

while (l1!=NULL || l2!=NULL){
x = getValueAndMoveNext(l1);
y = getValueAndMoveNext(l2);

sum = carry + x + y;

ListNode *node = new ListNode(sum%10);
*t = node;
t = (&node->next);

carry = sum/10;
}

if (carry > 0) {
ListNode *node = new ListNode(carry%10);
*t = node;
}

return h;
}
private:
int getValueAndMoveNext(ListNode* &l){
int x = 0;
if (l != NULL){
x = l->val;
l = l->next;
}
return x;
}
};


6. C 语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Definition for singly-linked list. */
struct ListNode {
int val;
struct ListNode *next;
};

static struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
int carry_num = 0;
int first = 1;
struct ListNode *res = NULL;
struct ListNode *p = NULL;
struct ListNode *prev = p;

while (l1 != NULL || l2 != NULL || carry_num) {
int sum = 0;
int last_carry = carry_num;
if (l1 != NULL) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != NULL) {
sum += l2->val;
l2 = l2->next;
}
if (sum >= 10) {
sum -= 10;
carry_num = 1;
} else {
carry_num = 0;
}

p = malloc(sizeof(*p));
if (first) {
res = p;
first = 0;
}
p->val = sum + last_carry;
if (p->val >= 10) {
p->val -= 10;
carry_num = 1;
}
p->next = NULL;
if (prev != NULL) {
prev->next = p;
}
prev = p;
}

return res;
}

static struct ListNode *node_build(const char *digits)
{
struct ListNode *res, *p, *prev;
int first = 1;
int len = strlen(digits);
const char *c = digits + len - 1;
prev = NULL;
while (len-- > 0) {
p = malloc(sizeof(*p));
if (first) {
first = 0;
res = p;
}
p->val = *c-- - '0';
p->next = NULL;
if (prev != NULL) {
prev->next = p;
}
prev = p;
}

return res;
}

static void show(struct ListNode *ln)
{
int sum = 0, factor = 1;
while (ln != NULL) {
sum += ln->val * factor;
factor *= 10;
ln = ln->next;
}
printf("%d
", sum);
}

int main(int argc, char **argv)
{
if (argc < 3) {
fprintf(stderr, "Usage: ./test n1 n2
");
exit(-1);
}

struct ListNode *l1 = node_build(argv[1]);
struct ListNode *l2 = node_build(argv[2]);
struct ListNode *res = addTwoNumbers(l1, l2);
show(l1);
show(l2);
show(res);
return 0;
}


--------------------------------------

0
0 收藏

0 评论
0 收藏
0