LeetCode 两数相加

题目

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

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

思路 1

两个链表不等长，那么在任一链表Next为nil时立刻跳出循环，再把长的链表加上去，最后把进位加上去，通俗，但是逻辑显得冗长拖沓。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  ret := &ListNode{}
  curpos := ret //循环指针

  overflow := 0         //进位
  sum := 0              //每次相加之和
  var tailpos *ListNode //未结束的链表指针

  for {
    sum = l1.Val + l2.Val + overflow
    overflow = 0
    if sum > 9 {
    overflow = 1
    sum = sum % 10
  }

  curpos.Val = sum

  l1 = l1.Next
  l2 = l2.Next

  //任一链表结束立刻跳出循环
  if l1 == nil {
    tailpos = l2
    break
  }
  if l2 == nil {
    tailpos = l1
    break
  }
  curpos.Next = &ListNode{}

  curpos = curpos.Next
  }

  if tailpos != nil {
    curpos.Next = &ListNode{}
    curpos = curpos.Next
    for {
      sum = tailpos.Val + overflow

      overflow = 0
      if sum > 9 {
        overflow = 1
        sum = sum % 10
      }

      curpos.Val = sum
      tailpos = tailpos.Next

      if tailpos == nil {
        break
      }
      curpos.Next = &ListNode{}
      curpos = curpos.Next
    }
  }
  if overflow != 0 {
    curpos.Next = &ListNode{Val: overflow, Next: nil}
  }

  return ret
}

思路 2

在之前的基础上稍微改进下，当遇到有结束的链表时，新建0值节点补齐，直到两个链表NEXT节点均为nil时再跳出循环，最后再补上进位。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  ret := &ListNode{}
  curpos := ret

  overflow := 0
  sum := 0

  for {
    sum = l1.Val + l2.Val + overflow
    overflow = 0
    if sum > 9 {
      overflow = 1
      sum = sum % 10
    }

    curpos.Val = sum

    l1 = l1.Next
    l2 = l2.Next

    if l1 == nil && l2 == nil {
      if overflow != 0 {
        curpos.Next = &ListNode{Val: overflow, Next: nil}
      }
      break
    }

    if l1 == nil {
      l1 = &ListNode{Val: 0, Next: nil}
    }

    if l2 == nil {
      l2 = &ListNode{Val: 0, Next: nil}
    }
    curpos.Next = &ListNode{}

    curpos = curpos.Next
  }

  return ret
}