Technology, life, programming, travel and money.

Picking the 5th from last element in a singly linked list

Here’s another of those fun coding interview puzzles. The kind that companies like Microsoft or Google might ask you. Given a singly linked list, select the 5th from last element. I’m writing the solution in C++ but the solution in Java would be almost identical. I’m also putting up my test code.

The restrictions are – you can only make one pass of the list, and you don’t know the length of the list.

First we need to define our linked list element. All it needs is to store a value, and a pointer to the next element in the list.

class Element
{
public:
	Element(int valueArg) : value(valueArg), next(NULL) {}
public:
	int value;
	Element* next;
};

Here is the actual solution. As we are only allowed one pass of the list we use two pointers. The second pointer trails 5 places behind the first pointer. When the first pointer reaches the end of the list we simply return whichever element the second pointer is pointing to.

We need to take care of the special case where the list has less than 5 elements – including the case where the list has 0 elements!

Element* FifthFromLast(Element* root)
{
	Element* current = root;
	int fromLast = 5;
	while (fromLast > 0 && current)
	{
		current = current->next;
		--fromLast;
	}
	if (fromLast != 0)
	{
		return NULL; // less than 5 items in list
	}
	Element* fifthFromLast = root;
	while (current)
	{
		current = current->next;
		fifthFromLast = fifthFromLast->next;
	}
	return fifthFromLast;
}

Here is the test code which tests the most common cases for this problem. As the parameter to FifthFromLast is the root element we can simulate a shorter list by passing in one of the middle elements.

void LinkedListTest()
{
	Element* one = new Element(1);
	Element* two = new Element(2);
	Element* three = new Element(3);
	Element* four = new Element(4);
	Element* five = new Element(5);
	Element* six = new Element(6);
	Element* seven = new Element(7);
	Element* eight = new Element(8);
	Element* nine = new Element(9);
	Element* ten = new Element(10);
	one->next = two;
	two->next = three;
	three->next = four;
	four->next = five;
	five->next = six;
	six->next = seven;
	seven->next = eight;
	eight->next = nine;
	nine->next = ten;
	cout << "Test: find 5th from last in 10 item list" << endl;
	Element* fifthFromLast = FifthFromLast(one);
	if (fifthFromLast == six)
	{
		cout << " Pass" << endl;
	}
	else
	{
		cout << "!Fail" << endl;
	}
	cout << "Test: with 4 item list - expect NULL" << endl;
	Element* nullReturnCheck = FifthFromLast(seven);
	if (nullReturnCheck == NULL)
	{
		cout << " Pass" << endl;
	}
	else
	{
		cout << "!Fail" << endl;
	}
	cout << "Test: FifthFromLast(NULL) - expect NULL" << endl;
	nullReturnCheck = FifthFromLast(NULL);
	if (nullReturnCheck == NULL)
	{
		cout << " Pass" << endl;
	}
	else
	{
		cout << "!Fail" << endl;
	}
	// clean up
	Element* current = one;
	while (current)
	{
		Element* next = current->next;
		delete current;
		current = next;
	}
}

This is the output from running the tests.

Test: find 5th from last in 10 item list
 Pass
Test: with 4 item list - expect NULL
 Pass
Test: FifthFromLast(NULL) - expect NULL
 Pass



Reader Feedback

3 Responses to “Picking the 5th from last element in a singly linked list”

  1. Shan says:

    Wow..interesting. Can you please write the same in C#? I am new to programming and would like to know how it looks in C#.

    you can email me at [snipped]

    Thanks,
    -Shan

  2. Enver says:

    I see you use “new” pretty often in your test code and you’re too lazy to “delete” (at least in Dijkstra, too).

    Why don’t you

    […]
    Element ten(10);
    one.next = two;
    […]

    so that instead of on the heap, you land your objects on the stack? You can still pass pointers if you wish, by doing
    FifthFromLast(&one);
    and similar.

    This way, being lazy is perfectly fine as the objects are destroyed by the runtime environment when you leave the local variables’ scope.

    Not that it makes much difference – but this way you get the “delete” for free and even save typing “new”.

  3. Enver says:

    Should have read
    one.next = &two;

    Sorry.

Leave a Reply

Do NOT fill this !