# 引言

题目链接:https://leetcode.com/problems/add-two-numbers/description/

# 题目大意

给出两个的倒序的链表,链表每个节点的值为非负个位数,链表反续串起来是一个数字,按照加法规则将两个链表相加并返回一个倒序链表,链表每个节点的数字对应计算结果的每一位。

例:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

Hint: You may assume the two numbers do not contain any leading zero, except the number 0 itself.

(不含前导零,数字本身可以为零)

# 题解

# 一句话题解

倒序链接正好由低位到高位表示了数字的每一位,直接取节点数据相加插入新链表节点即可 (注意进位问题)

复杂度 O(n)

# AC 代码

c++ 版本

class Solution
{
  public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *rList = NULL;
        ListNode *curNode;
        // 考虑进位
        int carry = 0;
        while (NULL != l1 || NULL != l2)
        {
            int var1 = (NULL != l1) ? l1->val : 0;
            int var2 = (NULL != l2) ? l2->val : 0;
            if (NULL == rList)
            {
                rList = new ListNode((var1 + var2 + carry) % 10);
                curNode = rList;
            }
            else
            {
                curNode->next = new ListNode((var1 + var2 + carry) % 10);
                curNode = curNode->next;
            }
            l1 = (NULL == l1) ? l1 : l1->next;
            l2 = (NULL == l2) ? l2 : l2->next;
            carry = (var1 + var2 + carry) / 10;
        }
        if (carry > 0)
        {
            curNode->next = new ListNode(carry);
        }
        return rList;
    }
};

go 版本 (感觉写的好挫,一点都不优雅 :[笑哭]:)

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var rList, curNode *ListNode
	var carry, var1, var2 int
	for nil != l1 || nil != l2 {
		if nil != l1 {
			var1 = l1.Val
			l1 = l1.Next
		} else {
			var1 = 0
		}
		if nil != l2 {
			var2 = l2.Val
			l2 = l2.Next
		} else {
			var2 = 0
		}
		if nil == rList {
			rList = &ListNode{(var1 + var2 + carry) % 10, nil}
			curNode = rList
		} else {
			curNode.Next = &ListNode{(var1 + var2 + carry) % 10, nil}
			curNode = curNode.Next
		}
		carry = (var1 + var2 + carry) / 10
	}
	if carry > 0 {
		curNode.Next = &ListNode{carry, nil}
	}
	return rList
}
更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

yx.zhang 微信支付

微信支付

yx.zhang 支付宝

支付宝