链表相加(二)

链表相加(二)_牛客题霸_牛客网

问题简述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。

思路1：转成数值计算（超时）

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        
        def get_v(cur):
            ret = 0
            while cur:
                ret = ret * 10 + cur.val
                cur = cur.next
            return ret
        
        s = get_v(head1) + get_v(head2)
        s = str(s)

        dummy = cur = ListNode(0)
        for c in s:
            cur.next = ListNode(int(c))
            cur = cur.next
            
        return dummy.next

思路2：利用栈

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        
        def get_v(x):
            ret = []
            while x:
                ret.append(x.val)
                x = x.next
            return ret
        
        h1 = get_v(head1)
        h2 = get_v(head2)
        
        ret = []
        ex = 0
        while h1 or h2:
            h1v = h1.pop() if h1 else 0
            h2v = h2.pop() if h2 else 0
            v = h1v + h2v + ex
            ret.append(v % 10)
            ex = v // 10
        
        if ex:
            ret.append(1)
            
        dummy = cur = ListNode(0)
        while ret:
            cur.next = ListNode(ret.pop())
            cur = cur.next
            
        return dummy.next

思路3：反转链表后逐位相加（推荐）

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        
        # def pp(x):
        #     """打印链表（调试用）"""
        #     tmp = []
        #     while x:
        #         tmp.append(x.val)
        #         x = x.next
        #     print(tmp)
        
        def reverse(x):
            """反转链表"""
            pre, cur = None, x
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
                
            return pre
        
        h1 = reverse(head1)
        h2 = reverse(head2)
        
        cur = dummy = ListNode(0)
        ex = 0  # 进位
        
        # 合并 h1 和 h2 的判断
        while h1 or h2:
            h1v = h1.val if h1 else 0
            h2v = h2.val if h2 else 0
            v = h1v + h2v + ex
            node = ListNode(v % 10)
            ex = v // 10
            cur.next = node
            cur = cur.next
            h1 = h1.next if h1 else None
            h2 = h2.next if h2 else None
        
        # 将下面两段合并到一起
        # ex = 0
        # while h1 and h2:
        #     v = h1.val + h2.val + ex
        #     node = ListNode(v % 10)
        #     ex = v // 10
        #     cur.next = node
        #     cur = cur.next
        #     h1 = h1.next
        #     h2 = h2.next
         
        # h = h1 if h1 else h2
        # while h:
        #     v = h.val + ex
        #     node = ListNode(v % 10)
        #     ex = v // 10
        #     cur.next = node
        #     cur = cur.next
        #     h = h.next
        
        # 如果还存在进位
        if ex:
            cur.next = ListNode(1)
        
        ret = dummy.next
        return reverse(ret)  # 注意最后再反转一次