Interview Questions

Find the middle element of a linked list

A linked list is a data structure which consists of a group of nodes where each node may point to some other node to form a sequence. Our nodes will have two fields:
## Node setup

**null**, which means we have reached the last node.
## Naive solution

A simple way to determine the middle node would be to fully pass through all nodes in the linked list and count how many elements there are in total. Then traverse the linked list again this time stopping at the total/2 node. For example, the first time you traverse the linked list your program determines there are 10 nodes, then the second pass through the linked list you stop at the 5th node, which is the middle node. This is a possible solution, but there is a faster way.
## Faster solution using 2 pointers

What we'll do is setup two pointers, one that will traverse the linked list one node at a time, and the other pointer will traverse two nodes at a time. This way when the faster pointer reaches the end of the linked list, the slower pointer will be halfway there because it was only moving one node at time while the faster one was moving two nodes at a time. This allows you to find the middle node of a linked list with only one pass, instead of passing through the whole linked list once, and then again to find the middle element.
## Running time

The running time of finding the middle element this way with two pointers is O(*n*) because once we pass through the entire linked list of n elements, the slower pointer is at the middle node already.
## Sources

http://www.careercup.com/question?id=1434688

(1) a "data" field which will store our data (string, number, etc.)
(2) a "next" field which will be a reference to some other node

Linked lists are useful and simple data structures and are sometimes preferred over using arrays because inserting or deleting elements can be done without reallocation or reorganization of the entire structure.
If, for example, you wanted to add an element to the beginning of the array, every single other element would need to be moved and the array would need to make space for one extra element. Inserting an element at the beginning of a linked list simply requires you to create a new node and set its "next" field to point to some node, making this new node the first node in the sequence now.
function Node(data, next) { this.data = data; this.next = next; }

class Node: def __init__(self, data, next): self.data = data self.next = nextThis is how we can then create a linked list with connecting nodes:

var n1 = new Node("Hello", null); var n2 = new Node("21", n1); var n3 = new Node("Green", n2); // assign a node to the head which functions // as the entry into our linked list var head = n3;

n1 = Node("Hello", None) n2 = Node("21", n1) n3 = Node("Green", n2) # assign a node to the head which functions # as the entry into our linked list head = n3Our challenge is to now find the middle node in a linked list. We don't initially know the length of a linked list, all we have is a single node which acts as the head of the linked list and which we can access all other nodes by traversing through each nodes "next" property. We can continuously loop through each node until we get to a node that has a "next" property of

function Node(data, next) { this.data = data; this.next = next; } // setup some nodes and connect them to each other // the linked list looks like: // (head) n5 -> n4 -> n3 -> n2 -> n1 -> null var n1 = new Node("Hello", null); var n2 = new Node("21", n1); var n3 = new Node("Green", n2); var n4 = new Node("Blue", n3); var n5 = new Node("Daniel", n4); // assign a node to the head which functions // as the entry into our linked list var head = n5; // setup pointers to both start // at the head of the linked list var fastPointer = head; var slowPointer = head; // loop through the linked list // when fastPointer reaches the end of the list // then slowPointer will be at the middle node while (fastPointer.next !== null && fastPointer.next.next !== null) { fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } // slowPointer is now at the middle node in the linked list slowPointer.data

class Node: def __init__(self, data, next): self.data = data self.next = next # setup some nodes and connect them to each other # the linked list looks like: # (head) n5 -> n4 -> n3 -> n2 -> n1 -> None n1 = Node("Hello", None) n2 = Node("21", n1) n3 = Node("Green", n2) n4 = Node("Blue", n3) n5 = Node("Daniel", n4) # assign a node to the head which functions # as the entry into our linked list head = n5 # setup pointers to both start # at the head of the linked list fastPointer = head slowPointer = head # loop through the linked list # when fastPointer reaches the end of the list # then slowPointer will be at the middle node while fastPointer.next != None and fastPointer.next.next != None: fastPointer = fastPointer.next.next slowPointer = slowPointer.next # slowPointer is now at the middle node in the linked list print slowPointer.data

mrdaniel
published this on 11/9/15 **|**

7

Nice Pass.
I was just wondering why can't we directly assign n5 to fastPointer and slowPointer rather than assigning n5 to head first?

kaizen

commented on 06/26/16

2

If that was directly done, it won't be as clear as now. For demostration purposes, head needs to be clearly defined. In fact, it took O(1) only, not a big deal.

arknamal

commented on 08/09/18

0

Ah one while loop instead of 2. Yeah my bad...

mrj936

commented on 09/15/18

0

How is this any better than traversing the entire thing? The two pointer jump is traversing the entire thing, to figure out how to jump twice it jumps once to get the next pointer then jumps again. Just because the code seems shorter does not mean this solution is faster, unless by faster you mean to type rather than to run. You still passed the link list twice, once fully with the "fast pointer" who still had to go through the nodes one by one on the low level to figure out how to path through, and once half a time with the slow pointer.
I must be missing something here, someone please explain to me why it is faster.

mrj936

commented on 09/15/18

0

class Node: def __init__(self, data, next): self.data=data self.next=next n1 = Node("Hello ,", None) n2 = Node("World, ", n1) n3 = Node("Gray", n2) head = n3 fastPointer=head slowPointer=head while fastPointer.next !=None and fastPointer ==None: fastPointer=fastPointer.next slowPointer=slowPointer.next print(slowPointer.data)

Garywei

commented on 09/04/18

0

@mrj936, the idea is that you are only looping over the list once. The pointer accesses inside the loop are fast operations and do not increase the time complexity of the algorithm (see https://en.wikipedia.org/wiki/Time_complexity)
The time complexity for this algorithm is O(n), where n is the number of entries in the list.
If you used an algorithm that traverses the list twice, it would be 2 * O(n), which has the same time complexity from a mathematical standpoint, but in practice would be up to twice as slow.

yossarian21

commented on 10/08/18

Log in to submit a comment.