一、简介

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

题目来源：牛客

二、实现

思路：考虑进位问题，所以需要从链表，最后面节点，依次往前，相加。首先，我们想到的是链表逆转后相加即可，其次，我们也可以借助栈，先进后出来实现。

下面是基于链表翻转实现：

/**
 *
 * @param head1 ListNode类
 * @param head2 ListNode类
 * @return ListNode类
 */
func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {
   // write code here
   if head1 == nil {
      return head2
   }

   if head2 == nil {
      return head1
   }

   head1 = revertList(head1)
   head2 = revertList(head2)

   var (
      newHead *ListNode
      flag int
   )

   for head1 != nil || head2 != nil {
      curVal := flag
      flag = 0
      if head1 != nil {
         curVal += head1.Val
         head1 = head1.Next
      }

      if head2 != nil {
         curVal += head2.Val
         head2 = head2.Next
      }

      if  curVal >= 10 {
         curVal = curVal - 10
         flag +=1 // 进位加1
      }

      newHead = &ListNode{
         Val: curVal,
         Next: newHead,
      }
   }

   // 这一步不能遗漏，进位可能还存在
   if flag != 0 {
      newHead = &ListNode{
         Val: flag,
         Next: newHead,
      }
   }

   return newHead
}

// 翻转链表
func revertList(head *ListNode) *ListNode {
   var newHead *ListNode
   for head != nil {
      nextNode := head.Next
      head.Next = newHead
      newHead = head
      head = nextNode
   }

   return newHead
}