LinkedList – Nth element

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 3^rd 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();
        }
    }
}

Advertisements