golang刷题1-两单链表数据相加

package main

import (
  "fmt"
  "strconv"
)

/**
题目如下：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

*/

//首先是有一个链表
type Node struct {
  value uint32
  next  *Node
}

type LinkNode struct {
  head *Node
}

/**
上面的题目我们做如下拆分
1：链表首先当然是循环，判断两个链表都是nil的情况则退出循环
2：链表循环过程中处理进位的问题，设置一个临时的进位变量，变量值是在next下加上
3：如果最后循环完了还有进一位的情况需要把最后的进一位的值补充到链表最后
4：最后循环链表生成字符串数字转换成数字

*/

func main() {
  link1 := &LinkNode{}
  link1.AddValue(2)
  link1.AddValue(4)
  link1.AddValue(3)

  link2 := &LinkNode{}
  link2.AddValue(5)
  link2.AddValue(6)
  link2.AddValue(4)

  fmt.Println(addTwoNum(link1.head, link2.head))

}

//添加链表
func (l *LinkNode) AddValue(value uint32) {
  if l.head == nil {
    node := Node{value: value}
    l.head = &node
    return
  }
  item := l.head
  for ; item.next != nil; item = item.next {
    if item.value == value {
      return
    }
  }
  //处理最后的一个链表连接
  if item.value == value {
    return
  }
  node := Node{value: value}
  item.next = &node
}

//翻转单链
func reserveLink(n *Node) *Node {
  if n == nil || n.next == nil {
    return n
  }
  //这个是递归执行函数
  new := reserveLink(n.next)
  //这里是从头节点开始下一个节点指向前一个节点
  n.next.next = n
  //这里是把原来的节点指向置空，相当于实现了翻转
  n.next = nil
  return new
}

func addTwoNum(l1 *Node, l2 *Node) (lastNum uint32) {
  tail := &LinkNode{}
  item := tail.head
  carry := uint32(0)
  //1.链表首先当然是循环，判断两个链表都是nil的情况则退出循环
  for l1 != nil || l2 != nil {
    n1 := uint32(0)
    n2 := uint32(0)
    if l1 != nil {
      n1 = l1.value
      l1 = l1.next
    }
    if l2 != nil {
      n2 = l2.value
      l2 = l2.next
    }
    //2：链表循环过程中处理进位的问题，设置一个临时的进位变量，变量值是在next下加上
    sum := n1 + n2 + carry
    sum, carry = sum%10, sum/10
    if item == nil {
      tail.head = &Node{value: sum}
      item = tail.head
    } else {
      item.next = &Node{value: sum}
      item = item.next
    }
  }
  //3：如果最后循环完了还有进一位的情况需要把最后的进一位的值补充到链表最后
  if carry > 0 {
    item.next = &Node{value: carry}
  }
  //4：最后循环链表生成字符串数字转换成数字,利用之前写的函数先翻转，再处理
  tail.head = reserveLink(tail.head)
  LastNumStr := ""
  item2 := tail.head
  if item2 != nil {
    for ; item2.next != nil; item2 = item2.next {
      LastNumStr = LastNumStr + strconv.Itoa(int(item2.value))
    }
    LastNumStr = LastNumStr + strconv.Itoa(int(item2.value))
  }
  tmp, _ := strconv.Atoi(LastNumStr)
  lastNum = uint32(tmp)
  return
}

/**
时间复杂度：O(\max(m,n))O(max(m,n))，其中 m,nm,n 为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1)O(1) 的时间。
空间复杂度：O(\max(m,n))O(max(m,n))。答案链表的长度最多为较长链表的长度 +1+1。
*/