本文概述
- C ++ 14
- Java
- Python3
- C#
- C
- C ++
- Java
- python
- C#
例如, 如果输入在列表下方且n = 3, 则输出为" B"
文章图片
推荐:请在"
实践
首先, 在继续解决方案之前。
【算法(如何获取链表的末尾开始为第n个节点的值())】方法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 = 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;
}// 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 = https://www.lsbin.com/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 = https://www.lsbin.com/new_data
self . next = Noneclass 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 variablelength = 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 = https://www.lsbin.com/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= 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;
}/* 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 = https://www.lsbin.com/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 = https://www.lsbin.com/data
self . next = Noneclass 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_nodedef 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)
returnref_ptr = ref_ptr. next
count + = 1if (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. nextprint "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 = https://www.lsbin.com/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是链表的长度。
如果你发现上述代码/算法有误, 请写评论, 或者找到其他解决相同问题的方法。
推荐阅读
- 算法设计(如何查找矩阵中的最大元素(详细实现))
- Python如何使用生成器(详细指南)
- 本文教你电脑打开黑屏原因排查
- 本文教你最容易让win10变回win7的办法
- win7激活工具最新推荐
- 2017最容易的win7pe工具最新推荐
- 安装系统 本文教你重装系统win7
- ie10中文版官方win7 64位最新推荐
- 系统之家win7旗舰版激活制作详细说明