本文概述
编写一个函数以计算给定单链表中的节点数。
例如, 对于链表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 = 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 rathbhupendraC
// 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 = 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 = 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 = 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#
// 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 = 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 = 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 = 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 = 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()C#
// 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 = 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输出如下：
count of nodes is 5本文作者：拉维。如果发现任何不正确的地方, 或者你想分享有关上述主题的更多信息, 请发表评论
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
