【Python】给定两个链表，分别表示两个非负整数。它们的数字逆序存储在链表中，且每个结点只存储一个数字，计算两个数的和，并且返回和的链表头指针

比眉伴天荒 2022-05-23 07:13 36阅读 0赞

### 链表相加 示例： ###

> 给定两个链表，分别表示两个非负整数。它们的数字逆序存储在链表中，且每个结点只存储一个数字，计算两个数的和，并且返回和的链表头指针。  
> 如：输入：2→4→3、5→6→4，输出：7→0→8

Python代码如下：

import numpy as np
    
    
    # 定义节点
    class SNode:
        Next = None
        Value = None
    
    
    # 创建带头结点的链表
    def createLinkList(size):
        if size <= 0:
            return None
        linkList = SNode()
        # 头插法
        for i in range(0, size):
            node = SNode()
            node.Value = np.random.randint(0, 9)
            node.Next = linkList.Next
            linkList.Next = node
        return linkList
    
    
    # 打印链表
    def printLinkList(linkList):
        if linkList == None:
            print('None')
            return
        s = "head"
        node = linkList.Next
        while node != None:
            s = s + "->" + str(node.Value)
            node = node.Next
        print(s)
    
    
    # 链表相加
    def Add(list1, list2):
        if list1 == None or list2 == None:
            return None
        node1 = list1.Next
        node2 = list2.Next
        # 进位
        carry = 0
        linkList = SNode()
        lnode = linkList
        while node1 and node2:
            newVaue = node1.Value + node2.Value + carry
            newNode = SNode()
            newNode.Value = newVaue % 10
            lnode.Next = newNode
            lnode = newNode
            carry = int(newVaue / 10)
            node1 = node1.Next
            node2 = node2.Next
    
        # 处理较长的链
        node = node2 if node1 == None else node1
        while node:
            newVaue = node.Value + carry
            newNode = SNode()
            newNode.Value = newVaue % 10
            lnode.Next = newNode
            lnode = newNode
            carry = int(newVaue / 10)
            node = node.Next
    
        # 处理可能的进位
        if carry != 0:
            lnode = SNode()
            lnode.Value = carry
    
        return linkList
    
    
    if __name__ == '__main__':
        linkList1 = createLinkList(5)
        linkList2 = createLinkList(9)
        printLinkList(linkList1)
        printLinkList(linkList2)
        linkList = Add(linkList1, linkList2)
        printLinkList(linkList)

输出结果：

head->3->6->7->4->3
    head->1->4->1->6->5->4->7->7->7
    head->4->0->9->0->9->4->7->7->7