如何将ListNode从LeetCode转换为常规列表？

Question

尝试解决LeetCode“添加两个数字”

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.

我编写了一个处理列表的程序，而LeetCode提供了ListNode。不幸的是，我无法理解ListNode机制（如何迭代，如何获得长度等等）。所以我决定把它转换成列表。请帮助我如何做，如何迭代所有ListNode并将其所有值放入常规列表，然后反过来：list->；ListNode以返回正确类型的答案

下面是我的一段代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l3 = [] #resulting list
        shift = 0 
        
        # HERE goes code for: ListNode -> List

        if len(l1) > len(l2):
            l_long = l1
            l_short = l2
        else:
            l_long = l2
            l_short = l1

谢谢大家!

Answer 1

您可以使用以下方法将可编辑性修补到这些链接列表中：

def ll_iter(node):
    while node:
        yield node.val
        node = node.next
ListNode.__iter__ = ll_iter

然后在代码中，您只需执行以下操作：

l1 = list(l1)

但我认为，编写一个直接使用链表的递归解决方案是最简单的。您甚至不会遇到递归深度问题，因为列表保证最多有100个节点

Answer 2

您应该阅读代码开头的文档，因为它为您提供了有关链表的解释。如果这还不够，我建议你退房。将链表转换为常规列表将使分配变得毫无意义。看见 this获取更多有关链表的资源

简而言之，链表满足了对无限数据结构的需求（当然，没有数据结构实际上是无限的，但链表肯定比数组更灵活）。链表由节点组成，每个节点指向下一个节点，最后一个节点指向null。这样，如果您想延长列表，只需创建一个新节点并使最后一个节点指向它即可。此外，每个节点都持有一个值。在问题中给出的实现中，self.val是每个节点的值持有者，self.next是指向下一个节点的指针

Answer 3

该问题不要求您使用常规列表。由于列表是以“相反顺序”存储的，这实际上很有帮助，因为您可以在两个列表之间分别添加数字，然后计算/携带从左向右移动的溢出量。例如，添加LinkedList [5, 1] + [5]会导致您向结果列表[0, 添加一个节点，然后迭代到下一个位置，将10s数字向前推进，然后从输入中执行1加上从上一次迭代的进位中执行1，得到2，因此结果是[0, 2]。如果将1带入9，则将进位数字再次向前移动

此外，如果你要建立一个常规的列表，你最好把它转换成一个int，然后做数学运算，把int转换成链表

但要将LinkedList转换为常规列表，而LinkedList类本身不是iterable类型，则如下所示

ll = ListNode(...)

l = []
n = ll
while n is not None:
    l.append(n.val)
    n = n.next

否则，如果它是一个合适的pythoniterable类型，[n.val for n in ll]