Nth Node from end of LinkedList

Find Nth Node from the end of a Linked List

 

There are many ways to perform this task but I would be discussing some of the ways which are optimized solution.

 

Assume we have list of m nodes and we need to find 2nd node from the mth node.

First Approach:
 

  • Scan the list and count the number of nodes. Let’s say its 10. i.e. m = 10
  • Now, m – 2 +1 which 10 – 2 +1 = 9th Node from the start (9th Node is the 2nd Node from the last i.e. 10th Node.)

 

Running Time complexity :

 

  • In first step,  we calculated the length of the List, we did a scan of the whole list i.e. O(n)
  • to perform the second step, we did a one more scan. i.e. O(n)

 
Total Complexity = O(n) + O(n) == O(n)
 

Space Complexity : Since we are not using any auxiliary data structures to hold the data, its O(1).

 
Here is the Code
 



package com.diaryreaders.datastructures.linkedlist;
public class NthNodeFromLinkedListEnd {
private int getNodesCount(DoublyLinkedList list) {
int count = 0;
while (list != null) {
count++;
list = list.getNext();
}
return count;
}
private int getNodeFromLast(DoublyLinkedList list, int count, int n) {
if (n < 1 || n > count) {
return -1;
}
count = count - n + 1;
for (int i = 1; i < count; i++) {
list = list.getNext();
}
return list.getData();
}
public static void main(String[] args) {
DoublyLinkedList dll1 = new DoublyLinkedList();
DoublyLinkedList dll2 = new DoublyLinkedList();
DoublyLinkedList dll3 = new DoublyLinkedList();
DoublyLinkedList dll4 = new DoublyLinkedList();
DoublyLinkedList dll5 = new DoublyLinkedList();
DoublyLinkedList dll6 = new DoublyLinkedList();
DoublyLinkedList dll7 = new DoublyLinkedList();
DoublyLinkedList dll8 = new DoublyLinkedList();
DoublyLinkedList dll9 = new DoublyLinkedList();
DoublyLinkedList dll10 = new DoublyLinkedList();
dll1.setPrev(null);
dll1.setNext(dll2);
dll1.setData(1);
dll2.setPrev(dll1);
dll2.setNext(dll3);
dll2.setData(2);
dll3.setPrev(dll2);
dll3.setNext(dll4);
dll3.setData(3);
dll4.setPrev(dll3);
dll4.setNext(dll5);
dll4.setData(4);
dll5.setPrev(dll4);
dll5.setNext(dll6);
dll5.setData(5);
dll6.setPrev(dll5);
dll6.setNext(dll7);
dll6.setData(6);
dll7.setPrev(dll6);
dll7.setNext(dll8);
dll7.setData(7);
dll8.setPrev(dll7);
dll8.setNext(dll9);
dll8.setData(8);
dll9.setPrev(dll8);
dll9.setNext(dll10);
dll9.setData(9);
dll10.setPrev(dll9);
dll10.setNext(null);
dll10.setData(10);
NthNodeFromLinkedListEnd nll = new NthNodeFromLinkedListEnd();
int count = nll.getNodesCount(dll1);
System.out.println(nll.getNodeFromLast(dll1, count, 6));
}
}


 
Output:

 

 Is there a way to get the results in one Scan?

 

In the above case, we did two scan to get the results. To improve this solution a bit more, we can complete this in only one scan.

 

  • Make two references of head. Say temp1 & temp2 both referring to head Node.
  • Start Temp1 to parse/iterate the list from the head Node and let it do this till it reaches nth steps from the head Node.
  • Start temp2 to parse/iterate the list from the head Node and start temp1 to iterate the list from the nth node.
  • Break the loop once temp1 reaches to null or end of the List. When temp1 reaches to end of the list, our temp2 reference would be at nth node from the last. Makes Sense.

 
Running Time complexity : O(n) 
 
Space Complexity : O(1)
 
Let’s see the code.
 



package com.diaryreaders.datastructures.linkedlist;
public class NthNodeFromLinkedListEnd {
private int getNodeFromLast(DoublyLinkedList list, int n) {
if (n < 1) {
return -1;
}
DoublyLinkedList currentNode = list;
for (int i = 0; i < n; i++) {
if (currentNode == null) {
return -1;
}
currentNode = currentNode.getNext();
}
while (currentNode != null) {
list = list.getNext();
currentNode = currentNode.getNext();
}
return list.getData();
}
public static void main(String[] args) {
DoublyLinkedList dll1 = new DoublyLinkedList();
DoublyLinkedList dll2 = new DoublyLinkedList();
DoublyLinkedList dll3 = new DoublyLinkedList();
DoublyLinkedList dll4 = new DoublyLinkedList();
DoublyLinkedList dll5 = new DoublyLinkedList();
DoublyLinkedList dll6 = new DoublyLinkedList();
DoublyLinkedList dll7 = new DoublyLinkedList();
DoublyLinkedList dll8 = new DoublyLinkedList();
DoublyLinkedList dll9 = new DoublyLinkedList();
DoublyLinkedList dll10 = new DoublyLinkedList();
dll1.setPrev(null);
dll1.setNext(dll2);
dll1.setData(1);
dll2.setPrev(dll1);
dll2.setNext(dll3);
dll2.setData(2);
dll3.setPrev(dll2);
dll3.setNext(dll4);
dll3.setData(3);
dll4.setPrev(dll3);
dll4.setNext(dll5);
dll4.setData(4);
dll5.setPrev(dll4);
dll5.setNext(dll6);
dll5.setData(5);
dll6.setPrev(dll5);
dll6.setNext(dll7);
dll6.setData(6);
dll7.setPrev(dll6);
dll7.setNext(dll8);
dll7.setData(7);
dll8.setPrev(dll7);
dll8.setNext(dll9);
dll8.setData(8);
dll9.setPrev(dll8);
dll9.setNext(dll10);
dll9.setData(9);
dll10.setPrev(dll9);
dll10.setNext(null);
dll10.setData(10);
NthNodeFromLinkedListEnd nll = new NthNodeFromLinkedListEnd();
System.out.println(nll.getNodeFromLast(dll1, 3));
}
}


 
Output:

No Comments Yet

Leave a Reply

Your email address will not be published.

Lorem ipsum dolor sit amet, consectetur a dipiscing elit. Vivamus leo ante,

FOLLOW US ON