算法：如何获取链表的末尾开始为第n个节点的值？

2021年3月20日14:27:47 发表评论 720 次浏览

本文概述

1)计算链表的长度。让长度为len。

2)从链表的开头打印第(len – n + 1)个节点。

C ++ 14

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

struct Node {
int data;
struct Node* next;
};

/* Function to get the nth node from the last of a linked list*/
void printNthFromLast( struct Node* head, int n)
{
int len = 0, i;

// count the number of nodes in Linked List
while (temp != NULL) {
temp = temp->next;
len++;
}

// check if value of n is not
// more than length of the linked list
if (len < n)
return ;

// get the (len-n+1)th node from the beginning
for (i = 1; i < len - n + 1; i++)
temp = temp->next;

cout << temp->data;

return ;
}

void push( struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new 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 */
}

// Driver Code
int main()
{

return 0;
}``````

Java

``````// Simple Java program to find n'th node from end of linked list

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

/* Function to get the nth node from the last of a
void printNthFromLast( int n)
{
int len = 0 ;

// 1) count the number of nodes in Linked List
while (temp != null ) {
temp = temp.next;
len++;
}

// check if value of n is not more than length of
if (len < n)
return ;

// 2) get the (len-n+1)th node from the beginning
for ( int i = 1 ; i < len - n + 1 ; i++)
temp = temp.next;

System.out.println(temp.data);
}

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

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

/*Driver program to test above methods */
public static void main(String[] args)
{
llist.push( 20 );
llist.push( 4 );
llist.push( 15 );
llist.push( 35 );

llist.printNthFromLast( 4 );
}
} // This code is contributed by Rajat Mishra``````

Python3

``````# Simple Python3 program to find
# n'th node from end
class Node:
def __init__( self , new_data):
self .data = new_data
self . next = None

def __init__( self ):

# createNode and and make linked list
def push( self , new_data):
new_node = Node(new_data)

# Function to get the nth node from
# the last of a linked list
def printNthFromLast( self , n):
temp = self .head # used temp variable

length = 0
while temp is not None :
temp = temp. next
length + = 1

# print count
if n > length: # if entered location is greater
# than length of linked list
print ( 'Location is greater than the' +
return
for i in range ( 0 , length - n):
temp = temp. next
print (temp.data)

# Driver Code
llist.push( 20 )
llist.push( 4 )
llist.push( 15 )
llist.push( 35 )
llist.printNthFromLast( 4 )

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

C#

``````// C# program to find n'th node from end of linked list
using System;

{

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

/* Function to get the nth node from the last of a
void printNthFromLast( int n)
{
int len = 0;

// 1) count the number of nodes in Linked List
while (temp != null )
{
temp = temp.next;
len++;
}

// check if value of n is not more than length of
if (len < n)
return ;

// 2) get the (len-n+1)th node from the beginning
for ( int i = 1; i < len - n + 1; i++)
temp = temp.next;

Console.WriteLine(temp.data);
}

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

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

/*Driver code */
public static void Main(String[] args)
{
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);

llist.printNthFromLast(4);
}
}

// This code is contributed by Rajput-Ji``````

``35``

C

``````void printNthFromLast( struct Node* head, int n)
{
static int i = 0;
return ;
if (++i == n)
}``````

O(n)其中n是链表的长度。

C ++

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

struct Node
{
int data;
struct Node* next;
};

/* Function to get the nth node
from the last of a linked list*/
void printNthFromLast( struct Node *head, int n)
{

int count = 0;
{
while ( count < n )
{
if (ref_ptr == NULL)
{
printf ( "%d is greater than the no. of "
"nodes in list" , n);
return ;
}
ref_ptr = ref_ptr->next;
count++;
} /* End of while*/

if (ref_ptr == NULL)
{
printf ( "Node no. %d from last is %d " , n, main_ptr->data);
}
else
{
while (ref_ptr != NULL)
{
main_ptr = main_ptr->next;
ref_ptr  = ref_ptr->next;
}
printf ( "Node no. %d from last is %d " , n, main_ptr->data);
}
}
}

// Function to push
void push( struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new 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 */
}

/* Driver program to test above function*/
int main()
{

}``````

Java

``````// Java program to find n'th
// node from end using slow and
// fast pointers
{

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

/* Function to get the
nth node from end of list */
void printNthFromLast( int n)
{

int count = 0 ;
{
while (count < n)
{
if (ref_ptr == null )
{
System.out.println(n
+ " is greater than the no "
+ " of nodes in the list" );
return ;
}
ref_ptr = ref_ptr.next;
count++;
}

if (ref_ptr == null )
{
System.out.println( "Node no. " + n +
" from last is " +
}
else
{

while (ref_ptr != null )
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
System.out.println( "Node no. " + n +
" from last is " +
main_ptr.data);
}
}
}

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

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

/*Driver program to test above methods */
public static void main(String[] args)
{
llist.push( 20 );
llist.push( 4 );
llist.push( 15 );
llist.push( 35 );

llist.printNthFromLast( 4 );
}
}
// This code is contributed by Rajat Mishra``````

python

``````# Python program to find n'th node from end using slow
# and fast pointer

# Node class
class Node:

# Constructor to initialize the node object
def __init__( self , data):
self .data = data
self . next = None

def __init__( self ):

# Function to insert a new node at the beginning
def push( self , new_data):
new_node = Node(new_data)

def printNthFromLast( self , n):

count = 0
if ( self .head is not None ):
while (count < n ):
if (ref_ptr is None ):
print " % d is greater than the
no. pf nodes in list " % (n)
return

ref_ptr = ref_ptr. next
count + = 1

if (ref_ptr is None ):
if ( self .head is not None ):
print "Node no. % d from last is % d "
% (n, main_ptr.data)
else :

while (ref_ptr is not None ):
main_ptr = main_ptr. next
ref_ptr = ref_ptr. next

print "Node no. % d from last is % d "
% (n, main_ptr.data)

# Driver program to test above function
llist.push( 20 )
llist.push( 4 )
llist.push( 15 )
llist.push( 35 )

llist.printNthFromLast( 4 )

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)``````

C#

``````// C# program to find n'th node from end using slow and
// fast pointerspublic
using System;

{

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

/* Function to get the nth node from end of list */
void printNthFromLast( int n)
{

int count = 0;
{
while (count < n)
{
if (ref_ptr == null )
{
Console.WriteLine(n + " is greater than the no "
+ " of nodes in the list" );
return ;
}
ref_ptr = ref_ptr.next;
count++;
}

if (ref_ptr == null )
{
Console.WriteLine( "Node no. " +
n + " from last is " +
main_ptr.data);
}
else
{
while (ref_ptr != null )
{
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
Console.WriteLine( "Node no. " +
n + " from last is " +
main_ptr.data);
}
}
}

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

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

/*Driver code */
public static void Main(String[] args)
{
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);

llist.printNthFromLast(4);
}
}

/* This code is contributed by PrinciRaj1992 */``````

``Node no. 4 from last is 35``

O(n)其中n是链表的长度。