本文概述
给定一个链表和一个数字n, 编写一个函数, 该函数从链表的末尾返回第n个节点的值。
例如, 如果输入在列表下方且n = 3, 则输出为" B"
推荐:请在"
实践
首先, 在继续解决方案之前。
方法1(使用链表的长度)
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;
/* Link list node */
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;
struct Node* temp = head;
// 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 ;
temp = head;
// 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 */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Driver Code
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
// create linked 35->15->4->20
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 35);
printNthFromLast(head, 4);
return 0;
}
Java
// Simple Java program to find n'th node from end of linked list
class LinkedList {
Node head; // head of the list
/* Linked List node */
class Node {
int data;
Node next;
Node( int d)
{
data = d;
next = null ;
}
}
/* Function to get the nth node from the last of a
linked list */
void printNthFromLast( int n)
{
int len = 0 ;
Node temp = head;
// 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
// the linked list
if (len < n)
return ;
temp = head;
// 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 */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver program to test above methods */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
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
class LinkedList:
def __init__( self ):
self .head = None
# createNode and and make linked list
def push( self , new_data):
new_node = Node(new_data)
new_node. next = self .head
self .head = new_node
# 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' +
' length of LinkedList' )
return
temp = self .head
for i in range ( 0 , length - n):
temp = temp. next
print (temp.data)
# Driver Code
llist = LinkedList()
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 LinkedList
{
public Node head; // head of the list
/* Linked List node */
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
linked list */
void printNthFromLast( int n)
{
int len = 0;
Node temp = head;
// 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
// the linked list
if (len < n)
return ;
temp = head;
// 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 */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver code */
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
}
}
// This code is contributed by Rajput-Ji
输出如下
35
以下是相同方法的递归C代码。感谢Anuj Bansal提供以下代码。
C
void printNthFromLast( struct Node* head, int n)
{
static int i = 0;
if (head == NULL)
return ;
printNthFromLast(head->next, n);
if (++i == n)
printf ( "%d" , head->data);
}
时间复杂度:
O(n)其中n是链表的长度。
方法2(使用两个指针)
维护两个指针–参考指针和主指针。初始化引用和主指向head的指针。首先, 将参考指针从头移到n个节点。现在, 将两个指针一一移动, 直到参考指针到达终点为止。现在, 主指针将从末尾指向第n个节点。返回主指针。
下图是上述方法的模拟:
下面是上述方法的实现:
C ++
// Simple C++ program to
// find n'th node from end
#include<bits/stdc++.h>
using namespace std;
/* Link list node */
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)
{
struct Node *main_ptr = head;
struct Node *ref_ptr = head;
int count = 0;
if (head != NULL)
{
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)
{
head = head->next;
if (head != 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 */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 35);
printNthFromLast(head, 4);
}
Java
// Java program to find n'th
// node from end using slow and
// fast pointers
class LinkedList
{
Node head; // head of the list
/* Linked List node */
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)
{
Node main_ptr = head;
Node ref_ptr = head;
int count = 0 ;
if (head != null )
{
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 )
{
head = head.next;
if (head != null )
System.out.println( "Node no. " + n +
" from last is " +
head.data);
}
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 */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver program to test above methods */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
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
class LinkedList:
# Function to initialize head
def __init__( self ):
self .head = None
# Function to insert a new node at the beginning
def push( self , new_data):
new_node = Node(new_data)
new_node. next = self .head
self .head = new_node
def printNthFromLast( self , n):
main_ptr = self .head
ref_ptr = self .head
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 ):
self .head = self .head. next
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 = LinkedList()
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 LinkedList
{
Node head; // head of the list
/* Linked List node */
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)
{
Node main_ptr = head;
Node ref_ptr = head;
int count = 0;
if (head != null )
{
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 )
{
head = head.next;
if (head != 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 */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver code */
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
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是链表的长度。
如果你发现上述代码/算法有误, 请写评论, 或者找到其他解决相同问题的方法。