Question: Devise an algorithm to determine the Nth-to-Last element in a singly linked list of unknown length. If N = 0, then your algorithm must return the last element.
Answer: Given that the only way to traverse a singly linked list is forwards from the head, it is not possible to just count N elements from the end of the linked list. Furthermore, the length of the linked list is unknown. We could traverse the list once to determine the number of elements and then traverse the list again to stop at the Nth element from the last element. But this seems a little inefficient. What if we could use 2 pointers?
So what if we use a current pointer and another pointer that is N elements behind the current pointer. When the current pointer reaches the end of the list, the second pointer will be pointing to the element N elements from the end of the list.
Here’s some code to illustrate this logic.
Node * findNToLastNode( Node *head, int N )
{
int i = 0;
Node *current, *behind;
current = head;
for( i = 0; i < N; i++ ) {
if( current->next ) {
current = current->next;
} else {
return NULL; // Length of the list is less than N
}
}
behind = head;
while( current->next ) {
current = current->next;
behind = behind->next;
}
return behind;
}
should it be i <= N ?
public Node tail(int N) {
Node explorer = head;
Node cursor = head;
for (int i = 0; i <= N; i++) {
explorer = explorer.next;
if (explorer.next == null) {
return null;
}
}
while (explorer!=null) {
cursor = cursor.next;
explorer = explorer.next;
}
return cursor;
}
Two things:
First, your if statement should be
if(current)
Also, your while loop condition should be
while(current)
Let’s say you have 3 elements and you want the 3rd to last element(which is the 1st element). Your code return null instead of returning the 1st element.
recursive solution with one function :
Node* findNToLastNode ( Node* head, int n )
{
static int _count ;
static Node* _pNode = NULL ;
if ( !head )
{
_count = 0 ;
return head ;
}
findNToLastNode(head->next, n) ;
if ( _count++ <= n) _pNode = head ;
return _pNode ;
}
Matthew, how would you do N-th to last… not necessarily second to last.
Oops, I made a mistake:
while( current->next )
{
if (current->next->next = NULL)
{
second_to_last = current
}
current = current->next;
}
Do it in one loop!
while( current->next )
{
current = current->next;
if (current->next->next = NULL)
{
second_to_last = current;
}
}
Have two pointers displacer, identifier
move the displacer initially to N positions
then move the identifier from start to the end and at each step moving the displacer too.
When the displacer reaches the end of the list the identifier will be at the N position from the last…
O(n):
Node * findR(Node *head, int N, int cur, int *n)
{
Node * res;
if(Nnext)
res = findR(head->next, N, cur+1, n);
else if(N>cur)
return NULL;
if(N<=cur && cur==*n)
res = head;
return res;
}
Node * findNToLastNode( Node *head, int N )
{
int n=0, cur=0;
return findR(head, N, cur, &n);
}
I think I’ve got a nice, short solution:
int nthtolast(list_t* list, int n) {
int len=0;
list_t* i=list;
while(list) {
if(len>n) i=i->next;
len++;
list=list->next;
}
return i->key;
}
Thoughts?
Firstly its not only cache behaviour thats this advantage, in OoO machine (every intel machine after pentium MMX with exception of atom) there is no dependence between the two traversals, so they can happen parallel in hardware, which should be by far closer to a speed of going it once than going it twice sequentially.
There is a way of doing it without traversing it twice, just write the addresses in array of size [n] and do modulo operation on counter to get index in the temp array, and if next is not null write the address to array else read the address from array and return it.
Anyway lists are evil. The pointers take lots of space in large addresspaces, and its traversal has data dependency that eliminates lots of automatic hardware parallerism at ipc level.
@Denis Molony: It is a single traversal. O(2*N) (2 to account for two pointers iterating through the list), which is in turn O(N).
@OP: Nice post.
Or you could reverse the initial list on the first traversal by popping off the elements as you read them and pushing them onto a new singly-linked list. Then read N items from the start of that list => L+N traversals.
Only useful if you don’t mind your singly-linked list ending up backwards, though 😉 I like your method better.
To all those people saying “you’re traversing it twice”: yes, but note that the solution presented above is much nicer on the cache, for reasonable n, than traversing the whole list twice.
Use 3 pointers: current, lastMark, secondLastMark.
Iterate through the list with current. Treat every (n+1)th element as a mark and note the last mark and second-to-last mark whenever encountering one. When you reach the end, figure out how far you have to step from secondLastMark to your answer, and do that.
You can do improve on this by leapfrogging. Have behind stay behind by at most N, and have behind2N stay behind at most 2N. Move behind and behind2N at N boundaries.
But you *are* traversing it twice.
current = current->next; // first traversal
behind = behind->next // second traversal
You could prove it by doing some timings.
If this was *really* a requirement, it would already be a doubly linked list.
So you still have to perform 2L-N link traversals, where L is the length of the list. For long lists, your version might have better cache behavior than first computing L and then advancing (L-N) steps.