本篇内容介绍了“如何实现数据结构与算法之两数相加”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
给定两个 非空 链表来表示两个非负整数。位数按照 逆序 方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入： (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 语言
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { var add = 0 , ans , head; while(l1 || l2) { var a = l1 ? l1.val : 0 , b = l2 ? l2.val : 0; var sum = a + b + add; add = ~~(sum / 10); var node = new ListNode(sum % 10); if (!ans) ans = head = node; else { head.next = node; head = node; } if (l1) l1 = l1.next; if (l2) l2 = l2.next; } if (add) { var node = new ListNode(add); head.next = node; head = node; } 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 def _addTwoNumbers(self, l1, l2): """ :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 def addTwoNumbers(self, l1, l2): 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 dummyHead = new ListNode(0); 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); } return dummyHead.next; }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; }“如何实现数据结构与算法之两数相加”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
