Posts Tagged ‘linked list’

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

Monday, August 18th, 2008

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


Tags:, , , ,
Posted in Programming | 3 Comments »

Reverse a linked list – C++ source code

Monday, July 21st, 2008

Reversing a linked list is a simple programming problem, which is often an interview question. In this case I’m referring to a singly linked list. I’ll provide the C++ solution and the C++ test code.

One of the easiest ways to reverse the linked list is to create a new head pointer, iterate through the list removing each item in turn and then inserting them at the beginning of the new list.

Here is the definition of my linked list node and the code to reverse the list.

class Node
{
public:
	Node(int value) : value(value), next(NULL) {}
public:
	int value;
	Node* next;
};
Node* reverseList(Node* head)
{
	Node* newList = NULL;
	Node* current = head;
	while (current)
	{
		Node* next = current->next;
		current->next = newList;
		newList = current;
		current = next;
	}
	return newList;
}

Below is the code I used to test this. This is what it does:

  1. It creates a simple linked list.
  2. Prints it out – output should be ‘12345’.
  3. Reverses it.
  4. Prints it out – output should be ‘54321’.
  5. Reverses it again.
  6. Prints it – output should be ‘12345’.
  7. Deletes the list.
void listTests()
{
	Node* one = new Node(1);
	Node* two = new Node(2);
	Node* three = new Node(3);
	Node* four = new Node(4);
	Node* five = new Node(5);
	one->next = two;
	two->next = three;
	three->next = four;
	four->next = five;
	Node* head = one;
	printList(head);
	head = reverseList(head);
	printList(head);
	head = reverseList(head);
	printList(head);
	// cleanup memory
	Node* current = head;
	while (current)
	{
		Node* next = current->next;
		delete current;
		current = next;
	}
}
void printList(Node* head)
{
	Node* current = head;
	while (current)
	{
		cout << current->value;
		current = current->next;
	}
	cout << endl;
}

This should be the output:

12345
54321
12345

If you are interested in other linked list related code I have a post about picking the 5th from last element from a singly linked list, and one on selecting random numbers from a stream or linked list. Both of these are based on programming interview questions.

Tags:, , , , ,
Posted in Programming | 8 Comments »