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