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

本文概述

C ++ 14
Java
Python3
C#
C
C ++
Java
python
C#

给定一个链表和一个数字n, 编写一个函数, 该函数从链表的末尾返回第n个节点的值。
例如, 如果输入在列表下方且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# 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# 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 */

输出如下