Given a Linked List and a number n, write a function that returns the value at the n’th node from the end of the Linked List.
For example, if the input is below list and n = 3, then output is “B”
Way 1 (Use length of linked list)
1) Calculate the length of Linked List. Let the length be len.
2) Print the (len – n + 1)th node from the beginning of the Linked List.
class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void printNthFromLast(int n)
{
int len = 0;
Node temp = head;
while (temp != null) {
temp = temp.next;
len++;
}
if (len < n)
return;
temp = head;
for (int i = 1; i < len - n + 1; i++)
temp = temp.next;
System.out.println(temp.data);
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
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);
}
}
|
Output
Following is a recursive C code for the same method.
static void printNthFromLast(Node head, int n)
{
static int i = 0;
if (head == null)
return;
printNthFromLast(head.next, n);
if (++i == n)
System.out.print(head.data);
}
|
Time Complexity: O(n) where n is the length of linked list.
Way 2 (Use two pointers)
Maintain two pointers – reference pointer and main pointer. Initialize both reference and main pointers to head. First, move the reference pointer to n nodes from head. Now move both pointers one by one until the reference pointer reaches the end. Now the main pointer will point to nth node from the end. Return the main pointer.
Below image is a dry run of the above approach:
class LinkedList
{
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
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)
{
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);
}
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
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);
}
}
|
Output
Node no. 4 from last is 35