尝试在Python 3中遍历链表

Question

我有一个奇怪的问题，无法遍历自定义链接列表。这是遍历的代码。

from typing import Optional

class ListNode:

    def __init__(self, val, next_node=None):

        self.val = val
        self.next_node = next_node

    @property
    def value(self):
        return self.val

    def __str__(self):
        return f"Value={self.val}, Next node available={self.next_node.value if self.next_node != None else -1}"

    __dict__ = ("val", "next_node",)

class Solution:

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[list]:

        result_arr = []

        l1_running = l1 != None
        curr_node = l1

        print("***** Start traversing L1 only ******")
        while l1_running:
            print(curr_node)
            if curr_node.next_node:
                l1_running = True
                curr_node = curr_node.next_node
            else:
                l1_running = False
                curr_node = None

        print("***** End traversing L1 only ******")
        print(result_arr)
        return result_arr

    def list_node_builder(self, l1: list[str], l2: list[int]) -> list[int]:

        print("***** Start building Linked List ******")
        l1_list_nodes = []
        l2_list_nodes = []

        for index, num in enumerate(l1):
            if index == len(l1) - 1:
                new_node = ListNode(num)
                l1_list_nodes.append(new_node)
                print(new_node)
            else:
                new_node = ListNode(num, ListNode(l1[index+1]))
                print(str(new_node))
                l1_list_nodes.append(new_node)

        for index, num in enumerate(l2):
            if index == len(l2) -1:
                l2_list_nodes.append(ListNode(num))
            else:
                l2_list_nodes.append(ListNode(num, ListNode(l2[index+1])))

        print("***** Done building Linked List ******")
        return self.addTwoNumbers(l1_list_nodes[0], l2_list_nodes[0])

当我尝试使用以下代码调用它时：

from addNumbers import Solution

if __name__ == "__main__":
    s = Solution()
    print(s.list_node_builder(l1=["a","b","c","d","e","f","g"], l2=[9,9,9,1]))

我的输出是这样的：

/Users/shyam/codespaces/python_projects/.venv/bin/python /Users/shyam/codespaces/python_projects/index.py 
***** Start building Linked List ******
Value=a, Next node available=b
Value=b, Next node available=c
Value=c, Next node available=d
Value=d, Next node available=e
Value=e, Next node available=f
Value=f, Next node available=g
Value=g, Next node available=-1
***** Done building Linked List ******
***** Start traversing L1 only ******
Value=a, Next node available=b
Value=b, Next node available=-1
***** End traversing L1 only ******
[]
[]

Process finished with exit code 0

我无法理解为什么构建链表看起来很好并且

next_node

设置正确，但是当我使用头遍历列表时，我在第二个节点上停止了。

Answer 1

那是因为您尝试将链表中的节点与要传递给的静态列表中的项目链接起来

list_node_builder

。您应该向 1l_list_nodes 添加一个节点，然后在添加新节点时，将最后一个节点链接到当前节点。这是代码（这应该可以回答您的问题，您仍然需要对代码的其余部分进行相应的更改）：

from typing import Optional

class ListNode:

    def __init__(self, val, next_node=None):

        self.val = val
        self.next_node = next_node

    @property
    def value(self):
        return self.val

    def __str__(self):
        return f"Value={self.val}, Next node available={self.next_node.value if self.next_node != None else -1}"

    __dict__ = ("val", "next_node",)

class Solution:

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[list]:

        result_arr = []

        l1_running = l1 != None
        curr_node = l1

        print("***** Start traversing L1 only ******")
        while l1_running:
            print(curr_node)
            if curr_node.next_node:
                l1_running = True
                curr_node = curr_node.next_node
            else:
                l1_running = False
                curr_node = None

        print("***** End traversing L1 only ******")
        print(result_arr)
        return result_arr

    def list_node_builder(self, l1: list[str], l2: list[int]) -> list[int]:

        print("***** Start building Linked List ******")
        l1_list_nodes = []
        l2_list_nodes = []

        # Here
        for index, num in enumerate(l1):
            new_node = ListNode(num)
            l1_list_nodes.append(new_node)
            if index !=0:
                l1_list_nodes[index-1].next_node = l1_list_nodes[index]

        for index, num in enumerate(l2):
            new_node = ListNode(num)
            l2_list_nodes.append(new_node)
            if index !=0:
                l2_list_nodes[index-1].next_node = l2_list_nodes[index]

        print("***** Done building Linked List ******")
        return self.addTwoNumbers(l1_list_nodes[0], l2_list_nodes[0])


if __name__ == "__main__":
    s = Solution()
    print(s.list_node_builder(l1=["a","b","c","d","e","f","g"], l2=[9,9,9,1]))