This is a classic interview question that I think most engineers should basically have memorized. Why; because it is a simple problem with a simple solution but very low level compared to our day to day activities. Doing stuff like this regularly even as a senior engineer is important exercise for your mind.
I have been asked this question half a dozen times in job interviews. If at some point in time in the future I am ever interviewing you, watch out for this question because I like to use it as an opener. (If you read my log and I am interviewing you, then I think you should have a leg up on the competition.)
Write an algorithm to find the middle node of the linked list. With the caveat that you can only make a single pass/loop through the list.
(think about it before you jump to see what the answer is)
.
..
...
....
.....
....
...
..
.
Disclaimer: Some people feel this is 1.5 list traversals despite using a single loop. This question and solution is not unique to this blog post so opinions of this are mixed. I respect that and you should form our only opinion,
The solution is straightforward once you step back and think slowly. Have two pointers that traverse the list but one of them only moves every other time. So by the time the faster moving pointer gets through the list, your second pointer is at the middle node.
The problem I ran into was... basic linked lists really aren't a part of normal libraries. I have never attempted taking this algorithm beyond pseudo code before so it was a fun little challenge to implement as simply as possible.
Pseudo Code
Node current = LinkedListHead;
int length = 0;
Node middle = LinkedListHead;
while(current.next() != null){
length++;
if(length % 2 == 0) {
middle = middle.next();
}
current = current.next();
}
return middle;
Java Solution
public class MiddleOfList {
public String findMiddleOfList() {
LinkedListNode tail = new LinkedListNode("data5", null);
LinkedListNode node4 = new LinkedListNode("data4", tail);
LinkedListNode node3 = new LinkedListNode("data3", node4);
LinkedListNode node2 = new LinkedListNode("data2", node3);
LinkedListNode head = new LinkedListNode("data1", node2);
return findMiddle(head);
}
private String findMiddle(LinkedListNode head) {
LinkedListNode current = head;
int length = 0;
LinkedListNode middle = head;
while(current.nextNode != null){
length++;
if(length % 2 == 0) {
middle = middle.nextNode;
}
current = current.nextNode;
}
return middle.data;
}
private class LinkedListNode {
public String data = null;
public LinkedListNode nextNode = null;
public LinkedListNode(String data, LinkedListNode nextNode) {
this.data = data;
this.nextNode = nextNode;
}
}
}
JavaScript Solution
Here is an implementation on JsFiddle. This is an attempt to keep things as simple as possible.
var tail = {data: "data5",next: null};
var node4 = {data: "data4",next: tail};
var node3 = {data: "data3",next: node4};
var node2 = {data: "data2",next: node3};
var head = {data: "data1",next: node2};
var current = head;
var length = 0;
var middle = head;
while (current.next != null) {
length++;
if (length % 2 == 0) {
middle = middle.next;
}
current = current.next;
}
console.log(middle);
Other Programming Challenges
