# 算法：编写函数以获取链表中的第N个节点

2021年4月11日15:40:06 发表评论 525 次浏览

## 本文概述

``````Input:  1->10->30->14, index = 2
Output: 30
The node at index 2 is 30``````

``````1. Initialize count = 0
2. Loop through the link list
a. if count is equal to the passed index then return current
node
b. Increment count
c. change current to point to next of the current.``````

## C ++

``````//C++ program to find n'th
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

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. */
{

//allocate node
Node* new_node = new Node();

//put in the data
new_node->data = new_data;

//off the new node

//to the new node
}

//as arguments and return
//data at index
{

//the index of the
//node we're currently
//looking at
int count = 0;
while (current != NULL) {
if (count == index)
return (current->data);
count++;
current = current->next;
}

/* if we get to this line, the caller was asking
for a non-existent element
so we assert fail */
assert (0);
}

//Driver Code
int main()
{

//empty list

//Use push() to construct
//below list
//1->12->1->4->1

//Check the count
//function
cout <<"Element at index 3 is " <<GetNth(head, 3);
return 0;
}

//This code is contributed by rathbhupendra``````

## C

``````//C program to find n'th
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

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;

//off the new node

//to the new node
}

//as arguments and return
//data at index
int GetNth( struct Node* head, int index)
{

//the index of the
//node we're currently
//looking at
int count = 0;
while (current != NULL) {
if (count == index)
return (current->data);
count++;
current = current->next;
}

/* if we get to this line, the caller was asking
for a non-existent element
so we assert fail */
assert (0);
}

//Driver Code
int main()
{

//empty list

//Use push() to construct
//below list
//1->12->1->4->1

//Check the count
//function
printf ( "Element at index 3 is %d" , GetNth(head, 3));
getchar ();
}``````

## Java

``````//Java program to find n'th node in linked list

class Node {
int data;
Node next;
Node( int d)
{
data = d;
next = null ;
}
}

/* Takes index as argument and return data at index*/
public int GetNth( int index)
{
int count = 0 ; /* index of Node we are
currently looking at */
while (current != null )
{
if (count == index)
return current.data;
count++;
current = current.next;
}

/* if we get to this line, the caller was asking
for a non-existent element so we assert fail */
assert ( false );
return 0 ;
}

/* Given a reference to the head of a list and an int, inserts a new Node on the front of the list. */
public void push( int new_data)
{

/* 1. alloc the Node and put data*/
Node new_Node = new Node(new_data);

/* 2. Make next of new Node as head */

/* 3. Move the head to point to new Node */
}

/* Driver code*/
public static void main(String[] args)
{

/* Use push() to construct below list
1->12->1->4->1  */
llist.push( 1 );
llist.push( 4 );
llist.push( 1 );
llist.push( 12 );
llist.push( 1 );

/* Check the count function */
System.out.println( "Element at index 3 is "
+ llist.GetNth( 3 ));
}
}``````

## python

``````# A complete working Python program to find n'th node

# 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

def __init__( self ):

# 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

# 4. Move the head to point to new Node

# Returns data at given index in linked list
def getNth( self , index):
current = self .head  # Initialise temp
count = 0  # Index of current node

# Loop while end of linked list is not reached
while (current):
if (count = = index):
return current.data
count + = 1
current = current. next

# if we get to this line, the caller was asking
# for a non-existent element so we assert fail
assert (false)
return 0

# Driver Code
if __name__ = = '__main__' :

# Use push() to construct below list
# 1->12->1->4->1
llist.push( 1 )
llist.push( 4 )
llist.push( 1 )
llist.push( 12 )
llist.push( 1 )

n = 3
print ( "Element at index 3 is :" , llist.getNth(n))``````

## C#

``````//C# program to find n'th node in linked list
using System;
using System.Diagnostics;

public class Node {
public int data;
public Node next;
public Node( int d)
{
data = d;
next = null ;
}
}

/* Takes index as argument and return data at index*/
public int GetNth( int index)
{
int count = 0; /* index of Node we are
currently looking at */
while (current != null ) {
if (count == index)
return current.data;
count++;
current = current.next;
}

/* if we get to this line, the caller was asking
for a non-existent element so we assert fail */
Debug.Assert( false );
return 0;
}

/* Given a reference to the head of a list and an int, inserts a new Node on the front of the list. */
public void push( int new_data)
{

/* 1. alloc the Node and put data*/
Node new_Node = new Node(new_data);

/* 2. Make next of new Node as head */

/* 3. Move the head to point to new Node */
}

/* Driver code*/
public static void Main(String[] args)
{

/* Use push() to construct below list
1->12->1->4->1 */
llist.push(1);
llist.push(4);
llist.push(1);
llist.push(12);
llist.push(1);

/* Check the count function */
Console.WriteLine( "Element at index 3 is "
+ llist.GetNth(3));
}
}

//This code is contributed by Arnab Kundu``````

``Element at index 3 is 4``

MY_DOOM

.

``````Algorithm
getnth(node, n)
1. Initialize count = 0
2. if count==n
return node->data
3. else
return getnth(node->next, n-1)``````

## C ++

``````//C program to find n'th node in linked list
//using recursion
#include <bits/stdc++.h>
using namespace std;

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 */

/* move the head to point to the new node */
}

as arguments and return data at index*/
int GetNth( struct Node* head, int n)
{
int count = 0;

//if count equal to n return node->data
if (count == n)

//recursively decrease n and increase
}

/* Driver code*/
int main()
{

/* Use push() to construct below list
1->12->1->4->1  */

/* Check the count function */
printf ( "Element at index 3 is %d" , GetNth(head, 3));
getchar ();
}``````

## Java

``````//Java program to find n'th node in linked list
//using recursion
class GFG {

static class Node {
int data;
Node next;
Node( int data) { this .data = data; }
}

/* 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. */
static Node push(Node head, int new_data)
{
/* allocate node */
Node new_node = new Node(new_data);

/* put in the data */
new_node.data = new_data;

}

as arguments and return data at index*/
static int GetNth(Node head, int n)
{
int count = 0 ;
if (head == null ) //edge case - if head is null
return - 1 ;
//if count equal too n return node.data
if (count == n)

//recursively decrease n and increase
return GetNth(head.next, n - 1 );
}

/* Driver code*/
public static void main(String args[])
{

/* Use push() to con below list
1.12.1.4.1 */

/* Check the count function */
System.out.printf( "Element at index 3 is %d" , GetNth(head, 3 ));
}
}
//This code is contributed by Arnab Kundu``````

## Python3

``````# Python3 program to find n'th node in

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

def __init__( self ):

''' 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. '''

def push( self , new_data):  # make new node and add
new_node = Node(new_data)

def getNth( self , llist, position):

# call recursive method

# recursive method to find Nth Node
def getNthNode( self , head, position, llist):
count = 0  # initialize count
if count = = position:  # if count is equal to position, # it means we have found the position
else :
llist.getNthNode(head. next , position - 1 , llist)
else :  # if head doesn't exist we have
print ( 'Index Doesn\'t exist' )

# Driver Code
if __name__ = = "__main__" :
llist.push( 1 )
llist.push( 4 )
llist.push( 1 )
llist.push( 12 )
llist.push( 1 )
# llist.getNth(llist, int(input()))
# Enter the node position here
# first argument is instance of LinkedList

print ( "Element at Index 3 is" , end = " " )
llist.getNth(llist, 3 )

# This code is contributed by Yogesh Joshi``````

## C#

``````//C# program to find n'th node in
using System;

class GFG {

public class Node {
public int data;
public Node next;
public Node( int data) { this .data = data; }
}

/* 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. */
static Node push(Node head, int new_data)
{
/* allocate node */
Node new_node = new Node(new_data);

/* put in the data */
new_node.data = new_data;

}

as arguments and return data at index*/
static int GetNth(Node head, int n)
{
//Base Condition
return -1;

int count = 0;

//if count equal too n return node.data
//Test Condition
if (count == n)

//recursively decrease n and increase
}

/* Driver code*/
public static void Main()
{

/* Use push() to con below list
1.12.1.4.1 */

/* Check the count function */
Console.Write( "Element at index 3 is {0}" , GetNth(head, 3));
}
}
/*Code improvement by Aishwarya Mittal*/
/* This code contributed by PrinciRaj1992 */``````

``Element at index 3 is 4``