2. Add Two Number

Leetcode 问题: 2. Add Two Number
Categories:
Tags:

题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

传入 2 个非空的链结资料 Link List，裡面是非负整数，数字储存方式是反向储存

数字 342 在链结储存方式就是 2 -> 4 -> 3

求两链结数字的的总和

答案

Golang

func addTwoNumbers(FirstNumberListNode *ListNode, SecondNumberListNode *ListNode) *ListNode {
	AnswerListNode := &ListNode{Val: 0}     // 建立答案节点，预设个位数是 0
	CurrentAnswerListNode := AnswerListNode // 目前答案节点
	number_1 := 0                           // 第 1 个加总数值
	number_2 := 0                           // 第 2 个加总数值
	carry_number := 0                       // 加总后的进位数值
	number_sum := 0                         // 加总数值

	// 若「第 1 数字节点」或「第 2 数字节点」有资料不为 nil 时，或没有任何进位数字时
	for FirstNumberListNode != nil || SecondNumberListNode != nil || carry_number != 0 {
		// 判断「第 1 数字节点」
		if FirstNumberListNode == nil {
			// 若「第 1 数字节点」为 nil，表示没有数字可以做加总了，设定可加总数字为 0
			number_1 = 0
		} else {
			// 若「第 1 数字节点」有值，将节点数值设定为此次第 1 个加总数值
			number_1 = FirstNumberListNode.Val
			FirstNumberListNode = FirstNumberListNode.Next
		}

		// 判断「第 2 数字节点」
		if SecondNumberListNode == nil {
			// 若「第 2 数字节点」为 nil，表示没有数字可以做加总了，设定可加总数字为 0
			number_2 = 0
		} else {
			// 若「第 1 数字节点」有值，将节点数值设定为此次第 2 个加总数值
			number_2 = SecondNumberListNode.Val
			SecondNumberListNode = SecondNumberListNode.Next
		}

		// 加总数值
		number_sum = (number_1 + number_2 + carry_number)

		// 设定馀数为目前答案节点数值
		CurrentAnswerListNode.Next = &ListNode{Val: number_sum % 10}

		// 设定答案节点的下一节点为目前节点，继续往后做加总
		CurrentAnswerListNode = CurrentAnswerListNode.Next

		// 取得加总后的进位数值，继续往后做加总
		carry_number = number_sum / 10
	}
	return AnswerListNode.Next
}

完整程式码

package main

import (
	"fmt"
)

// ListNode define
type ListNode struct {
	Val  int
	Next *ListNode
}

// 问题
type question struct {
	parameter
	answer
}

// para 是参数
// one 代表第一个参数
type parameter struct {
	one     []int
	another []int
}

// ans 是答案
// one 代表第一个答案
type answer struct {
	one []int
}

func main() {

	// 问题清单
	question_list := []question{

		{
			parameter{[]int{}, []int{}},
			answer{[]int{}},
		},

		{
			parameter{[]int{1}, []int{1}},
			answer{[]int{2}},
		},

		{
			parameter{[]int{1, 2, 3, 4}, []int{1, 2, 3, 4}},
			answer{[]int{2, 4, 6, 8}},
		},

		{
			parameter{[]int{1, 2, 3, 4, 5}, []int{1, 2, 3, 4, 5}},
			answer{[]int{2, 4, 6, 8, 0, 1}},
		},

		{
			parameter{[]int{1}, []int{9, 9, 9, 9, 9}},
			answer{[]int{0, 0, 0, 0, 0, 1}},
		},

		{
			parameter{[]int{9, 9, 9, 9, 9}, []int{1}},
			answer{[]int{0, 0, 0, 0, 0, 1}},
		},

		{
			parameter{[]int{2, 4, 3}, []int{5, 6, 4}},
			answer{[]int{7, 0, 8}},
		},

		{
			parameter{[]int{1, 8, 3}, []int{7, 1}},
			answer{[]int{8, 9, 3}},
		},
	}

	fmt.Printf("------------------------Leetcode Problem 2------------------------\n")

	for _, question := range question_list {
		param := question.parameter
		fmt.Printf("【input】:%v       【output】:%v\n", param, List2Ints(addTwoNumbers(Ints2List(param.one), Ints2List(param.another))))
	}
	fmt.Printf("\n\n\n")
}

// 连结数字相加
func addTwoNumbers(FirstNumberListNode *ListNode, SecondNumberListNode *ListNode) *ListNode {
	AnswerListNode := &ListNode{Val: 0}     // 建立答案节点，预设个位数是 0
	CurrentAnswerListNode := AnswerListNode // 目前答案节点
	number_1 := 0                           // 第 1 个加总数值
	number_2 := 0                           // 第 2 个加总数值
	carry_number := 0                       // 加总后的进位数值
	number_sum := 0                         // 加总数值

	// 若「第 1 数字节点」或「第 2 数字节点」有资料不为 nil 时，或没有任何进位数字时
	for FirstNumberListNode != nil || SecondNumberListNode != nil || carry_number != 0 {
		// 判断「第 1 数字节点」
		if FirstNumberListNode == nil {
			// 若「第 1 数字节点」为 nil，表示没有数字可以做加总了，设定可加总数字为 0
			number_1 = 0
		} else {
			// 若「第 1 数字节点」有值，将节点数值设定为此次第 1 个加总数值
			number_1 = FirstNumberListNode.Val
			FirstNumberListNode = FirstNumberListNode.Next
		}

		// 判断「第 2 数字节点」
		if SecondNumberListNode == nil {
			// 若「第 2 数字节点」为 nil，表示没有数字可以做加总了，设定可加总数字为 0
			number_2 = 0
		} else {
			// 若「第 1 数字节点」有值，将节点数值设定为此次第 2 个加总数值
			number_2 = SecondNumberListNode.Val
			SecondNumberListNode = SecondNumberListNode.Next
		}

		// 加总数值
		number_sum = (number_1 + number_2 + carry_number)

		// 设定馀数为目前答案节点数值
		CurrentAnswerListNode.Next = &ListNode{Val: number_sum % 10}

		// 设定答案节点的下一节点为目前节点，继续往后做加总
		CurrentAnswerListNode = CurrentAnswerListNode.Next

		// 取得加总后的进位数值，继续往后做加总
		carry_number = number_sum / 10
	}
	return AnswerListNode.Next
}

// 链结清单转换成整数阵列
func List2Ints(HeadListNode *ListNode) []int {
	// 链结深度限制，链结深度超过限制会出错
	link_list_depth_limit := 100

	current_link_list_depth := 0

	res := []int{}
	for HeadListNode != nil {
		// 若有连结资料
		current_link_list_depth++
		if current_link_list_depth > link_list_depth_limit {
			msg := fmt.Sprintf("链结深度超过%d，可能出现环状链结。检查错误，或者调整 List2Ints 函式中 link_list_depth_limit 的限制。", link_list_depth_limit)
			panic(msg)
		}

		res = append(res, HeadListNode.Val)
		HeadListNode = HeadListNode.Next
	}

	return res
}

// Ints2List convert []int to List
// 整数阵列转换成链结清单
func Ints2List(nums_list []int) *ListNode {
	if len(nums_list) == 0 {
		return nil
	}

	// 初始化链结节点
	HeadListNode := &ListNode{}
	// 设定目前链结节点
	CurrentListNode := HeadListNode
	for _, number := range nums_list {
		// 设定链结节点的下一节点
		CurrentListNode.Next = &ListNode{Val: number}
		// 将下一节点设为目前节点
		CurrentListNode = CurrentListNode.Next
	}
	return HeadListNode.Next
}

Python

from typing import List


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    @staticmethod
    # ListNode 转换成数字清单
    def listNodeToNumList(HeadListNode: ListNode) -> List[int]:
        # 数字清单
        num_list = []
        while HeadListNode is not None:
            num_list.append(HeadListNode.val)
            HeadListNode = HeadListNode.next

        return num_list

    @staticmethod
    # 数字清单转换成 ListNode
    def numListToListNode(nums_list: List[int]) -> ListNode:
        # 初始化链结节点
        HeadListNode = ListNode(None)

        # 设定目前链结节点
        CurrentListNode = HeadListNode
        for value in nums_list:
            # 设定链结节点的下一节点
            CurrentListNode.next = ListNode(value)
            # 将下一节点设为目前节点
            CurrentListNode = CurrentListNode.next

        return HeadListNode.next

    def addTwoNumbers(self, FirstNumberListNode: ListNode, SecondNumberListNode: ListNode) -> ListNode:
        # 建立答案节点，预设个位数是 0
        AnswerListNode = ListNode(0)
        CurrentAnswerListNode = AnswerListNode  # 目前答案节点
        number_1: int = 0  # 第 1 个加总数值
        number_2: int = 0  # 第 2 个加总数值
        carry_number: int = 0  # 加总后的进位数值
        number_sum: int = 0  # 加总数值

        while FirstNumberListNode is not None or SecondNumberListNode is not None or carry_number != 0:
            # === 计算第 1 个数字 ===
            if FirstNumberListNode is None:
                # 若「第 1 数字节点」为 nil，表示没有数字可以做加总了，设定可加总数字为 0
                number_1 = 0
            else:
                # 若「第 1 数字节点」有值，将节点数值设定为此次第 1 个加总数值
                number_1 = FirstNumberListNode.val
                FirstNumberListNode = FirstNumberListNode.next

            # === 计算第 2 个数字 ===
            if SecondNumberListNode is None:
                # 若「第 2 数字节点」为 nil，表示没有数字可以做加总了，设定可加总数字为 0
                number_2 = 0
            else:
                number_2 = SecondNumberListNode.val
                SecondNumberListNode = SecondNumberListNode.next

            # 加总数值
            number_sum = number_1 + number_2 + carry_number
            # 设定馀数为目前答案节点数值
            CurrentAnswerListNode.next = ListNode(number_sum % 10)
            # 设定答案节点的下一节点为目前节点，继续往后做加总
            CurrentAnswerListNode = CurrentAnswerListNode.next
            # 取得加总后的进位数值，继续往后做加总
            carry_number = int(number_sum / 10)

        return AnswerListNode.next


if __name__ == '__main__':
    # begin
    s = Solution()
    print(s.listNodeToNumList(s.addTwoNumbers(s.numListToListNode([2, 4, 3]), s.numListToListNode([5, 6, 4]))))
    print(s.listNodeToNumList(
        s.addTwoNumbers(s.numListToListNode([9, 9, 9, 9, 9, 9, 9]), s.numListToListNode([9, 9, 9, 9]))))

参考资料