VietMX Staff asked 3 years ago
Use lockstep solution. The key to this algorithm is to set two pointers p1 and p2 apart by n-1 nodes initially so we want p2 to point to the (n-1)th node from the start of the list then we move p2 till it reaches the last node of the list. Once p2 reaches end of the list p1 will be pointing to the Nth node from the end of the list.
This lockstep approach will generally give better cache utilization, because a node hit by the front pointer may still be in cache when the rear pointer reaches it. In a language implementation using tracing garbage collection, this approach also avoids unnecessarily keeping the beginning (thus entire) list live for the duration of the operation.
Another solution is to use circular buffer. Keep a circular buffer of size x and add the nodes to it as you traverse the list. When you reach the end of the list, the x’th one from the tail is equal to the next entry in the circular buffer.
The lockstep approach moves all array elements in every step, resulting in a O(n + x2) running time, whereas circular buffer approach uses a circular array and runs in O(n). The circular buffer solution requires an additional x in memory.
// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
// If list does not exist or if there are no elements in the list,return NULL
if (head == null || n < 1) {
return null;
}
// make pointers p1 and p2 point to the start of the list.
LinkedListNode p1 = head;
LinkedListNode p2 = head;
// The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
// so we want p2 to point to the (n-1)th node from the start of the list
// then we move p2 till it reaches the last node of the list.
// Once p2 reaches end of the list p1 will be pointing to the nth node
// from the end of the list.
// loop to move p2.
for (int j = 0; j < n - 1; ++j) {
// while moving p2 check if it becomes NULL, that is if it reaches the end
// of the list. That would mean the list has less than n nodes, so its not
// possible to find nth from last, so return NULL.
if (p2 == null) {
return null;
}
// move p2 forward.
p2 = p2.next;
}
// at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
// till p2 reaches the last node in the list.
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
// at this point p2 has reached the last node in the list and p1 will be
// pointing to the nth node from the last..so return it.
return p1;
}Circular buffer approach:
Node getNodeFromTail(Node head, int x) {
// Circular buffer with current index of of iteration.
int[] buffer = new int[x];
int i = 0;
do {
// Place the current head in its position in the buffer and increment
// the head and the index, continuing if necessary.
buffer[i++ % x] = head;
head = head.next;
} while (head.next != NULL);
// If we haven't reached x nodes, return NULL, otherwise the next item in the
// circular buffer holds the item from x heads ago.
return (i < x) ? NULL : buffer[++i % x];
}