目录
两个链表生成相加链表
访问量:925

一、简介

假设链表中每一个节点的值都在 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
}