reviewmylife

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