Python 中链表的长度

---

为了计算链表的长度，我们遍历列表，计算每个节点，直到到达末尾，下一个节点为None。假设我们有一个单链表，我们需要找到它的长度。链表具有 next 和 val 字段。因此，如果输入类似于 [2 -> 4 -> 5 -> 7 -> 8 -> 9 -> 3]，则输出将为 7。两种常用的查找链表长度的方法如下：

• 迭代方法：涉及到遍历链表，并使用额外的变量来计数链表中的节点数。

• 递归方法：以节点作为参数，并自身调用下一个节点，直到到达链表的末尾。

使用迭代方法

使用迭代方法查找链表长度的一些步骤。

• 初始化计数器

• 遍历链表

• 返回计数

初始化计数器

首先将计数器count设置为 0。此变量将跟踪我们在链表中遇到的节点数。

# Initialize the counter to zero
class Solution:
    def solve(self, node):
        count = 0

遍历链表。

使用while循环，我们从头节点遍历链表到每个其他节点。在跟随后续引用到达下一个节点之前，每个节点的计数器增加 1。

# Traverse until the node is not None
while node:  
    count += 1  
    node = node.next  

返回计数

当节点变为None时，循环停止，这表示链表的结尾。最后，返回计数器的值，以获得链表的长度。

return count

示例

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    ptr = head
    for element in elements[1:]:
        new_node = ListNode(element)
        ptr.next = new_node
        ptr = ptr.next
    return head

class Solution:
    def solve(self, node):
        count = 0
        while node:
            count += 1
            node = node.next
        return count

ob = Solution()
head = make_list([2, 4, 5, 7, 8, 9, 3])
print(ob.solve(head))  

输出

7

使用递归方法

使用递归方法查找链表长度的一些步骤

• 链表节点定义

• 基本情况

• 递归情况

• 返回总计数

定义链表节点

考虑一个类Node，它定义了一个链表节点，具有数据值data和对列表中下一个节点的引用next。

# Linked List Node definition
class Node:
    def __init__(self, new_data):
        self.data = new_data  
        self.next = None  

基本情况

当递归到达head == None的节点时，它停止并返回0。这表示列表的结尾。

if head is None:
    return 0 

递归情况

否则，我们将当前节点计为 1，并递归地对下一个节点(head.next)调用该函数，收集总计数，直到到达基本情况。

return 1 + count_nodes(head.next) 

返回总计数

到达基本情况后，每次递归调用都会返回链表中的节点总数。

# Driver code to test the function
if __name__ == "__main__":
    head = Node(2)
    head.next = Node(4)
    head.next.next = Node(5)
    head.next.next.next = Node(7)
    head.next.next.next.next = Node(8)
	head.next.next.next.next.next = Node(9)
	head.next.next.next.next.next.next = Node(3)
	
    # Function call to count the number of nodes
    print("Count of nodes is", count_nodes(head))

示例

# Linked List Node
class Node:
    def __init__(self, new_data):
        self.data = new_data
        self.next = None

# Recursively count number of nodes in linked list
def count_nodes(head):
    # Base Case
    if head is None:
        return 0

    # Count this node plus the rest of the list
    return 1 + count_nodes(head.next)


# Driver code
if __name__ == "__main__":
    head = Node(1)
    head.next = Node(3)
    head.next.next = Node(1)
    head.next.next.next = Node(2)
    head.next.next.next.next = Node(1)

    # Function call to count the number of nodes
    print("Count of nodes is", count_nodes(head))

输出

Count of nodes is 5