【LintCode 简单】167. 链表求和

浅浅的花香味﹌ 2022-11-28 13:28 116阅读 0赞

1.问题描述：

你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中`相反`的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。

2.样例：

> 样例 1:
> 
> 输入: 7->1->6->null, 5->9->2->null  
> 输出: 2->1->9->null      
> 样例解释: 617 + 295 = 912, 912 转换成链表:  2->1->9->null  
> 样例 2:
> 
> 输入:  3->1->5->null, 5->9->2->null  
> 输出: 8->0->8->null      
> 样例解释: 513 + 295 = 808, 808 转换成链表: 8->0->8->null

3.代码：

"""
    Definition of ListNode
    class ListNode(object):
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    """
    
    
    class Solution:
        """
        @param l1: the first list
        @param l2: the second list
        @return: the sum list of l1 and l2
        """
    
        def addLists(self, l1, l2):
            # write your code here
            if l1 is None: return l2
            if l2 is None: return l1
    
            h1 = l1
            h2 = l2
            # 只有两个链表的下一个节点数都为None,退出循环
            while h1.next is not None or h2.next is not None:
                # 若只有一条链表的下一个节点为None，补充为0,不影响后续的加法结果
                if h1.next == None: h1.next = ListNode(0)
                if h2.next == None: h2.next = ListNode(0)
                h1.val = h1.val + h2.val
                # 当加结果>=10,当前结果节点为个位数，下一个节点+1
                if h1.val >= 10:
                    h1.val = h1.val % 10
                    h1.next.val += 1
                h1 = h1.next
                h2 = h2.next
            else:
                h1.val = h1.val + h2.val
                # 链表尾部的计算，如果>=10，则在尾部再添加一个节点
                if h1.val >= 10:
                    h1.val = h1.val % 10
                    h1.next = ListNode(1)
            return l1

这道题有考察关于链表结构的使用，链表中每个结点都有一个值val，然后可以使用next来获取下一个结点。这里要注意的一点是，在循环前，将两个链表复制了取到头结点h1和h2中，之后的操作都是在h1和h2中做的。而且有使用next来获取下一个结点也是赋值给了h1和h2。但是最后返回的结果是存储在l1中，返回l1。

参考资料：

1. [https://blog.csdn.net/xiongxu3381/article/details/77961567][https_blog.csdn.net_xiongxu3381_article_details_77961567]

[https_blog.csdn.net_xiongxu3381_article_details_77961567]: https://blog.csdn.net/xiongxu3381/article/details/77961567