xisto Community

# Data Structures -- Linked List Find the nth last element in linked list.

## Recommended Posts

Given a linked list, find the 5th last element with Time complexity O(n) and minimal space complexity.

Note: If you know the answer and if you feel it is simple also please post the answers so that others will come to know about the answers.

There are various kinds of linked lists available and can be implemented in many languages and in different ways.

Linked lists are used as a building block for many other data structures, such as stacks, queues and their variations.

The "data" field of a node can be another linked list. By this device, one can construct many linked data structures with lists; this practice originated in the Lisp programming language, where linked lists are a primary (though by no means the only) data structure, and is now a common feature of the functional programming style.

Sometimes, linked lists are used to implement associative arrays, and are in this context called association lists. There is very little good to be said about this use of linked lists; they are easily outperformed by other data structures such as self-balancing binary search trees even on small data sets (see the discussion in associative array). However, sometimes a linked list is dynamically created out of a subset of nodes in such a tree, and used to more efficiently traverse that set.

even bad solutions are welcome... .

##### Share on other sites

Hmm, presuming a singly linked list where you can't start at the end and work your way back, you could use a circular buffer with 5 elements (e.g. an array that can store the contents of the LL nodes) and traverse the list until you reach the end ... then, the "next" element in your circular buffer is the fifth last.

E.g.:

for (i=0; (e = next element) != null; i++%5) {

buf = e

}

fifth_last = buf

Something like that I guess. You'd also need to initialise your array to null and check for this at the end in case your LL < 5 elements.

##### Share on other sites

yours is a nice solution... Better in usage of memory also. This circular buffer thing is very good.

What is i am giving you a constraint of

1. "NO EXTRA MEMORY"

Give a solution with the above constraints.

Small Hint:

Do not make it complex...think very simple. --> for a simple solution.

##### Share on other sites

Ok.. here is a very simple solutionHave two pointers.Initially, let both the pointers point to the first node of the linked listNow move one of the pointers to the 5th node of the linked list.This can be done in O(1) complexity i.e. constant time.Example:-1-->2-->3-->4-->5-->6-->7-->8-->9-->10->11-->12Here, one pointer points to 5 while the other pointer points to 1Now keep moving each pointer i.e. current node to next node, until the first pointer reaches the end of the linked list i.e. 12The second pointer will now be pointing to the 5th last element i.e. 8

##### Share on other sites

\$item= \$array[count(\$array)-5];untestedmay need to perform this in steps though\$num = count(\$array);\$n = \$num - 5;\$item = \$array[ \$n ];

##### Share on other sites

@sanjay0828Good one... the expected solution.Again... i want a simpler solution. What will be the basic answer that comes to your mind if i give this problem.??Very basic.. ..If no answer i will be posting it in my next post.

##### Share on other sites

Use two variable (sum4 and sum5) to store the sum of last 4 nodes and last 5 nodes respectively. At the end of the loop, the 5th node data = sum5 - sum4.-Grant

##### Share on other sites

while(ptr->next->next->next->next->next!=NULL) ptr=ptr->next; //after loop, ptr points to the fifth last element in the list;

##### Share on other sites

reverse the list and find the 5th element from the start,Not simple though just an idea.Varalu,Can u plz post what's the simple idea ?Thanks

##### Share on other sites

How to find the number of element in circular link list

Hi All,

If I have a circular link list and I want to count the no of element within it.I donot want to use first_pointer==last_pointer method.

Is there any other approach to count the element?

Thanks

Sarkar

##### Share on other sites

running sample program using stack implementing link list

Hi to all!...Gud day!...

I'm new to this site, but I find it

Interesting to find out the

Opinion of others, specially regarding

Programming...

I really needed someone to

Help me with this,...

I've got to have a sample

Running program of "STACK IMPLEMENTING LINK LIST",

Even just a simple one!

I'm badly in need of that!!...

Pls...

Hope I can find solutions

To my probs through this site!!...

I'll be waiting for some reply through here

Or you can email me @ leane_crazycute18 at yahoo.Com

Thank you and God bless!

-question by leane

##### Share on other sites

@sanjay0828Good one... the expected solution.

Again... i want a simpler solution. What will be the basic answer that comes to your mind if i give this problem.??
Very basic.. ..

If no answer i will be posting it in my next post.

the most basic and the only answer that came to my mind (actually, my frnd's mind. I am too laazy to use mine)  is to find length and then to find the (l-n)th element with o(n2) complexity.

##### Share on other sites

the most basic and the only answer that came to my mind (actually, my frnd's mind. I am too laazy to use mine)  is to find length and then to find the (l-n)th element with o(n2) complexity.

This is similar to finding the middle element in the link list with slight variation..

1. Have two pointer initially ( first and second )

2. move the second pointer alone 5 nodes.

3. Now move both the pointers one node at a time until the second reaches the end.

when the second reaches the end , the first node will be the 5th last element..

`node * first ,*second;first = second = root;// moves the second ptr 5 nodes..int i =0;while ( (i < 5) && (second != NULL) ){	second = second-> next;	i++;}while( second->next != NULL ){	   first = first->next;	   second = second->next;}return (first) ; // first ptr is the 5th node from the last..`

The above solution is same as the one Sanjay gave. This algorithm can be even generalized to find the kth node from the last similarly....

But the answer that i expected is below..

Just scan the list twice.

You can get the kth element from the last.

This algorithm is known as hare and tortoise algorithm.

##### Share on other sites

But the answer that i expected is below..

Just scan the list twice.

You can get the kth element from the last.

This algorithm is known as hare and tortoise algorithm.

That's same as what I said... In first scan, find the length and in second scan, find the required element. This seems to be only tortoise-tortoise scan.

The other answer (your and sanjay's answer) is more efficient with worst case operations half of what is required in first answer. complexity will be o(n) in both cases. (my bad. i had to edit. i mentioned complexity o(n^2) incorrectly.)

Thanks for the problem.

Edited by vivek.m (see edit history)

##### Share on other sites
main class problem..Data Structures -- Linked List

hello..It's my first time here to visit..I want to ask for help in making a main class of my linked list in queue..Here's what is asking for:

If the input satisfies partial ordering, then the algorithm will terminate when theQueue is empty? If a loop exists, it will also terminate but will not output the elements in theLoop. Instead, it will just inform the user that a loop is present:

here's the code:

interface Queue{   /* Insert an item */   void enqueue(Object item) throws QueueException;   /* Delete an item */   Object dequeue() throws QueueException;}Class QueueException extends RuntimeException{   public QueueException(String err){     super(err);   }}

another file:

class LinkedQueue implements Queue{   Node front, rear;   /* Create an empty queue */   LinkedQueue(){   }   /* Create a queue with node and initially */   LinkedQueue(Node and){     front = and;     rear = and;   }   /* Inserts an item onto the queue */   public void enqueue(Object item){     Node and = new Node(item, null);     if (front == null) {       front = and;       rear = and;     }     else{       rear.Link = and;       rear = and;     }   }   /* Deletes an item from the queue */   public Object dequeue() throws QueueException{     Object x;     if (front == null) throw new QueueException             ("Retrieving from an empty queue.");       x = front.Info;     front = front.Link;     return x;   }   /* Main method to test the queue */   public static void main(String args[]){     LinkedQueue q = new LinkedQueue();     for (int I=11; I>0; I--){       q.Enqueue(new Integer(I));       System.Out.Println(I +" inserted");     }     for (int I=12; I>0; I--)       System.Out.Println(q.Dequeue() + " retrieved");   }}

thank you...God Bless

## Create an account

Register a new account