leetcode - 两数相加（含单向链表构建、检索）

两数相加

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

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

链接：原题链接

解法

• 思路：设置一个进位标记位 carry（默认为0），当位数之和 >=10 时候，carry 置 1；且每次位数相加时，加上 carry

  func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  	// 从低位到高位遍历
  	var sum ListNode
  	cursor1 := l1
  	cursor2 := l2
  	// 用于保存 sum 尾部的地址
  	cursorSum := &sum
  	// 进位标志位
  	carry := 0
  	for {
  		if cursor1 != nil || cursor2 != nil || carry >0 {
  			// 单个位相加的值
  			byteSum := 0
  			if cursor1 != nil {
  				byteSum = byteSum + cursor1.Val
  				cursor1 = cursor1.Next
  			}
  			if cursor2 != nil {
  				byteSum = byteSum + cursor2.Val
  				cursor2 = cursor2.Next
  			}
              cursorSum.Next = new(ListNode)
              cursorSum = cursorSum.Next
  			cursorSum.Val, carry = (byteSum+ carry)%10, (byteSum+ carry)/10
  			continue
  		}
  		break
  	}
  	return sum.Next
  }

  时间复杂度：O(N)
  空间复杂度：O(N)

补充

题目中假定已经存在两个链表 l1 与 l2，实际在测试用例时，是需要自己构造这两个单向链表的，下面则给出构造单向链表的方法：

构造链表：

func CreateNodeList(slice []int) ListNode {
	var listNode ListNode
	length := len(slice)
        // 游标指针
	cursor := &listNode
        // 构造到第 length-1 个 Listnode,保证 Next 为列表中的最后一个节点  
	for index, value := range slice {
		if index == length - 1{
			break
		}
		var nextNode *ListNode
		cursor.Val = value
		nextNode = &ListNode{
			Val: slice[index+1],
			Next: nil,
		}
		cursor.Next = nextNode
		cursor = nextNode
	}
	return listNode
}

遍历链表：

func PrintList(node *ListNode)  {
	var cursor *ListNode
	cursor = node
	for {
		if cursor.Next != nil {
			fmt.Println(*cursor)
		}else {
			fmt.Println(*cursor)
			break
		}
		cursor = cursor.Next
	}
}

用例：

func main()  {
	// 测试用例的数组，并将数组转化成链表
	arryA:= []int{2, 4, 3, 5, 6}
	arryB:= []int{4, 9, 3, 1, 4}
    
	listNodeA := CreateNodeList(arryA)
	PrintList(&listNodeA)
    
	listNodeB := CreateNodeList(arryB)
	PrintList(&listNodeB)

	listNodeSum := addTwoNumbers(&listNodeA, &listNodeB)
	PrintList(listNodeSum)
}