算法设计（查找链表的长度（迭代和递归）） _数据结构

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C ++
C
Java
python
C#
C / C ++
Java
python
C#

编写一个函数以计算给定单链表中的节点数。

文章图片
例如, 对于链表1-> 3-> 1-> 2-> 1, 该函数应返回5。
推荐：请在"实践首先, 在继续解决方案之前。迭代解

1) Initialize count as 0 2) Initialize a node pointer, current = head. 3) Do following while current is not NULL a) current = current -> next b) count++; 4) Return count

以下是上述算法的实现, 以找到节点数。
C ++

// Iterative C++ program to find length // or count of nodes in a linked list #include < bits/stdc++.h> using namespace std; /* Link list node */ class Node { public : int data; Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node-> data = https://www.lsbin.com/new_data; /* link the old list off the new node */ new_node-> next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Counts no. of nodes in linked list */ int getCount(Node* head) { int count = 0; // Initialize count Node* current = head; // Initialize current while (current != NULL) { count++; current = current-> next; } return count; } /* Driver program to test count function*/ int main() { /* Start with the empty list */ Node* head = NULL; /* Use push() to construct below list 1-> 2-> 1-> 3-> 1 */ push(& head, 1); push(& head, 3); push(& head, 1); push(& head, 2); push(& head, 1); /* Check the count function */ cout< <"count of nodes is " < < getCount(head); return 0; } // This is code is contributed by rathbhupendra

// Iterative C program to find length or count of nodes in a linked list #include< stdio.h> #include< stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data*/ new_node-> data= https://www.lsbin.com/new_data; /* link the old list off the new node */ new_node-> next = (*head_ref); /* move the head to point to the new node */ (*head_ref)= new_node; }/* Counts no. of nodes in linked list */ int getCount( struct Node* head) { int count = 0; // Initialize count struct Node* current = head; // Initialize current while (current != NULL) { count++; current = current-> next; } return count; }/* Driver program to test count function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct below list 1-> 2-> 1-> 3-> 1*/ push(& head, 1); push(& head, 3); push(& head, 1); push(& head, 2); push(& head, 1); /* Check the count function */ printf ("count of nodes is %d" , getCount(head)); return 0; }

Java

// Java program to count number of nodes in a linked list/* Linked list Node*/ class Node { int data; Node next; Node( int d){ data = https://www.lsbin.com/d; next = null ; } }// Linked List class class LinkedList { Node head; // head of list/* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }/* Returns count of nodes in linked list */ public int getCount() { Node temp = head; int count = 0 ; while (temp != null ) { count++; temp = temp.next; } return count; }/* Driver program to test above functions. Ideally this function should be in a separate user class. It is kept here to keep code compact */ public static void main(String[] args) { /* Start with the empty list */ LinkedList llist = new LinkedList(); llist.push( 1 ); llist.push( 3 ); llist.push( 1 ); llist.push( 2 ); llist.push( 1 ); System.out.println("Count of nodes is " + llist.getCount()); } }

python

# A complete working Python program to find length of a # Linked List iteratively# Node class class Node: # Function to initialise the node object def __init__( self , data): self .data = https://www.lsbin.com/data # Assign data self . next = None # Initialize next as null# Linked List class contains a Node object class LinkedList:# Function to initialize head def __init__( self ): self .head = None# This function is in LinkedList class. It inserts # a new node at the beginning of Linked List. def push( self , new_data):# 1 & 2: Allocate the Node & #Put in the data new_node = Node(new_data)# 3. Make next of new Node as head new_node. next = self .head# 4. Move the head to point to new Node self .head = new_node# This function counts number of nodes in Linked List # iteratively, given'node' as starting node. def getCount( self ): temp = self .head # Initialise temp count = 0 # Initialise count# Loop while end of linked list is not reached while (temp): count + = 1 temp = temp. next return count# Code execution starts here if __name__ = = '__main__' : llist = LinkedList() llist.push( 1 ) llist.push( 3 ) llist.push( 1 ) llist.push( 2 ) llist.push( 1 ) print ( "Count of nodes is :" , llist.getCount())

// C# program to count number // of nodes in a linked list using System; /* Linked list Node*/ public class Node { public int data; public Node next; public Node( int d) { data = https://www.lsbin.com/d; next = null ; } }// Linked List class public class LinkedList { Node head; // head of list/* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }/* Returns count of nodes in linked list */ public int getCount() { Node temp = head; int count = 0; while (temp != null ) { count++; temp = temp.next; } return count; }/* Driver program to test above functions. Ideally this function should be in a separate user class. It is kept here to keep code compact */ public static void Main() { /* Start with the empty list */ LinkedList llist = new LinkedList(); llist.push(1); llist.push(3); llist.push(1); llist.push(2); llist.push(1); Console.WriteLine("Count of nodes is " + llist.getCount()); } }/* This code contributed by PrinciRaj1992 */

输出如下：

count of nodes is 5

递归解

int getCount(head) 1) If head is NULL, return 0. 2) Else return 1 + getCount(head-> next)

以下是上述算法的实现, 以找到节点数。
C / C ++

// Recursive C program to find length or count of nodes in a linked list #include< stdio.h> #include< stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data*/ new_node-> data= https://www.lsbin.com/new_data; /* link the old list off the new node */ new_node-> next = (*head_ref); /* move the head to point to the new node */ (*head_ref)= new_node; }/* Counts the no. of occurrences of a node (search_for) in a linked list (head)*/ int getCount( struct Node* head) { // Base case if (head == NULL) return 0; // count is 1 + count of remaining list return 1 + getCount(head-> next); }/* Driver program to test count function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct below list 1-> 2-> 1-> 3-> 1*/ push(& head, 1); push(& head, 3); push(& head, 1); push(& head, 2); push(& head, 1); /* Check the count function */ printf ("count of nodes is %d" , getCount(head)); return 0; }

Java

// Recursive Java program to count number of nodes in // a linked list/* Linked list Node*/ class Node { int data; Node next; Node( int d){ data = https://www.lsbin.com/d; next = null ; } }// Linked List class class LinkedList { Node head; // head of list/* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }/* Returns count of nodes in linked list */ public int getCountRec(Node node) { // Base case if (node == null ) return 0 ; // Count is this node plus rest of the list return 1 + getCountRec(node.next); }/* Wrapper over getCountRec() */ public int getCount() { return getCountRec(head); }/* Driver program to test above functions. Ideally this function should be in a separate user class. It is kept here to keep code compact */ public static void main(String[] args) { /* Start with the empty list */ LinkedList llist = new LinkedList(); llist.push( 1 ); llist.push( 3 ); llist.push( 1 ); llist.push( 2 ); llist.push( 1 ); System.out.println("Count of nodes is " + llist.getCount()); } }

python

# A complete working Python program to find length of a # Linked List recursively# Node class class Node: # Function to initialise the node object def __init__( self , data): self .data = https://www.lsbin.com/data# Assign data self . next = None# Initialize next as null# Linked List class contains a Node object class LinkedList:# Function to initialize head def __init__( self ): self .head = None# This function is in LinkedList class. It inserts # a new node at the beginning of Linked List. def push( self , new_data):# 1 & 2: Allocate the Node & #Put in the data new_node = Node(new_data)# 3. Make next of new Node as head new_node. next = self .head# 4. Move the head to point to new Node self .head = new_node# This function counts number of nodes in Linked List # recursively, given'node' as starting node. def getCountRec( self , node): if ( not node): # Base case return 0 else : return 1 + self .getCountRec(node. next )# A wrapper over getCountRec() def getCount( self ): return self .getCountRec( self .head)# Code execution starts here if __name__ = = '__main__' : llist = LinkedList() llist.push( 1 ) llist.push( 3 ) llist.push( 1 ) llist.push( 2 ) llist.push( 1 ) print 'Count of nodes is :' , llist.getCount()

// Recursive C# program to count number of nodes in // a linked list using System; /* Linked list Node*/ public class Node { public int data; public Node next; public Node( int d) { data = https://www.lsbin.com/d; next = null ; } } // Linked List class public class LinkedList { Node head; // head of list /* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Returns count of nodes in linked list */ public int getCountRec(Node node) { // Base case if (node == null ) return 0; // Count is this node plus rest of the list return 1 + getCountRec(node.next); } /* Wrapper over getCountRec() */ public int getCount() { return getCountRec(head); } /* Driver program to test above functions. Ideally this function should be in a separate user class. It is kept here to keep code compact */ public static void Main(String[] args) { /* Start with the empty list */ LinkedList llist = new LinkedList(); llist.push(1); llist.push(3); llist.push(1); llist.push(2); llist.push(1); Console.WriteLine("Count of nodes is " + llist.getCount()); } } // This code is contributed 29AjayKumar

输出如下：