本文共 1675 字，大约阅读时间需要 5 分钟。

目录

题目描述

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

输入/输出示例

解决方案

因为两个链表是单向链表，且是从个位数开始至最高位存储的每一个数字，因此依次对两个链表的每一位做加法即可。

在做加法的时候需要注意一点，如果两个数相加超过了9，必须向更高位进位，即高位+1。如果高位+1后继续大于9，重复进位，直至小于10。

需要考虑的一点是，两个数长度不相等的情况。如果一个链表遍历结束，则等待另一个链表全部遍历完后计算才可以结束。

代码

package maintype ListNode struct {	Val  int	Next *ListNode}func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {	head := &ListNode{Val: 0}	pre := head	sum := 0	for {		if l1 == nil && l2 == nil && sum == 0 {			break		}		value1 := 0		value2 := 0		if l1 != nil {			value1 = l1.Val		}		if l2 != nil {			value2 = l2.Val		}		sum += value1 + value2		pre.Next = &ListNode{Val: sum % 10}		pre = pre.Next		sum = sum / 10		if l1 != nil {			l1 = l1.Next		}		if l2 != nil {			l2 = l2.Next		}	}	return head.Next}

代码走读

package main// 链表节点type ListNode struct {   Val  int   Next *ListNode}func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {   // 定义一个新链表的表头和指针。新链表用来保存最终的计算结果   head := &ListNode{Val: 0}   pre := head    // 每一步求和的暂存变量   sum := 0   for {      if l1 == nil && l2 == nil && sum == 0 {         break      }      value1 := 0      value2 := 0      if l1 != nil {         value1 = l1.Val      }      if l2 != nil {         value2 = l2.Val      }      // 每一步的求和结果      sum += value1 + value2      // 创建新的节点，将sum值的个位作为新节点的值      pre.Next = &ListNode{Val: sum % 10}      pre = pre.Next      // 保留sum的十位数，作为进位数保留到下一步计算中      sum = sum / 10      if l1 != nil {         l1 = l1.Next      }      if l2 != nil {         l2 = l2.Next      }   }   return head.Next}

传送门

转载地址：http://mdsoi.baihongyu.com/