QUES:
Consider a singly linked list. What is the optimal way to traverse to an Nth element from the last element of that singly linked list. Any algorithms or logic to achieve in optimal way?
Naive soln :
- First find the total number of nodes, by iterating the entire list ..
- Now subtract the nth last node from the total number
- Now again iterate from the head node to the nth node…
But it require two complete iteration..
Optimized soln :
- Create two pointers and point those pointers to head node..
- Iterate first pointer to nth node..
- Now, iterate both first node pointer and second node pointer, until first node pointer reaches the end of the list .. Now second pointer will be pointing to the nth node from the last node..
List :
We need to find 3rd from the last, that is 40
80 | 70 | 60 | 50 | 40 | 30 | 20 |
P1 – pointer 1 & P2- pointer 2 both pointing to head node
P1,P2 -80 | 70 | 60 | 50 | 40 | 30 | 20 |
P1 Iterate first pointer to nth node.. ie n=3
P2 – 80 | 70 | P1 – 60 | 50 | 40 | 30 | 20 |
Iterate both first node pointer and second node pointer, until first node pointer reaches the end of the list
80 | 70 | 60 | 50 | P2 – 40 | 30 | P1 – 20 |
Program :
/** * * @author vignesh_v */ class LinkedList { LinkedList nextNode; int data; LinkedList(int data) { this.data = data; } void display() { System.out.println("Value " + data); } } class LinkedListCreation { LinkedList firstNode; LinkedListCreation() { firstNode = null; } //Adding datas to LinkedList void insert(int data) { LinkedList list = new LinkedList(data); list.nextNode = firstNode; firstNode = list; } void display() { LinkedList currentNode = firstNode; while (currentNode != null) { currentNode.display(); currentNode = currentNode.nextNode; } } LinkedList findNthLast(int n) { //Create two pointers and point those pointers to head node.. LinkedList pointerNode1 = firstNode; LinkedList pointerNode2 = firstNode; //Iterate first pointer to nth node.. for (int i = 1; i < n; i++) { if (pointerNode1 == null) { return null; } else { pointerNode1 = pointerNode1.nextNode; } } //Iterate both first node pointer and second node pointer, //until first node pointer reaches the end of the list .. //Now second pointer will be pointing to the nth node from //the last node.. while (pointerNode1.nextNode != null) { pointerNode1 = pointerNode1.nextNode; pointerNode2 = pointerNode2.nextNode; } //nthLastNode return pointerNode2; } } public class TestLinkedList { public static void main(String[] a) { LinkedListCreation listCreation = new LinkedListCreation(); listCreation.insert(20); listCreation.insert(30); listCreation.insert(40); listCreation.insert(50); listCreation.insert(60); listCreation.insert(70); listCreation.insert(80); listCreation.display(); LinkedList listFound = listCreation.findNthLast(3); if (listFound != null) { listFound.display(); } } }
THanks! This is a good page too:
http://www.programmerinterview.com/index.php/data-structures/find-nth-to-last-element-in-a-linked-list/