Find the middle element of the linked list in single pass – O(n) complexity

A linked list contains Nodes that are linked to each other.

Create a Node – A node consists of data of that node and some information about the next linked node

function Node(data, nextNode){
this.data = data;
this.nextNode = nextNode;
}

Create all nodes

Note: First Node from right. This would be our last node in sequence. The reference to next node would be null since this is our last node.

var n5 = new Node("5", null); 
var n4 = new Node("4", n5);
var n3 = new Node("3", n4);
var n2 = new Node("2", n3);
var n1 = new Node("1", n2);

// So here is the representation of the linked list nodes, that we just created.
// n1 (1, n2) –> n2 (2, n3) –> n3 (3, n4) –> n4 (4, n5) –> n5 (5, null)

Here is how the linked list looks

linkedlist

The Naive Solution to this problem would be in 2 passes (2 for loops), which takes O(n^2) worst case complexity

1st pass is to loop thru to get the count of nodes in linked list and
2nd pass is to loop thru find the middle element by dividing the Count of Nodes by 2

So, for example if there are 5 Nodes.

1st pass is to count the number of nodes = 5
2nd pass is to loop thru to get the middle element by dividing 5/2 = 2.5 (so in the middle element to be 3)

There is a better and a faster way to get this in 1 Pass (1 for/while loop), with O(n) complexity

Assign 2 pointers while looping.
1st pointer moves 1 element at a time.
2nd pointer moves 2 elements at a time (twice as faster as the 1st pointer)

Some theory/story:

Assume that Person A and Person B would like to reach a destination X from same starting point.

Assume that it would actually take 10 mins to reach destination X.

Assume that Person B walks 2 times faster than Person A, then by the time Person B reaches destination X, Person A is exactly half way thru.

So, lets give a starting point to our node n1.

var slowNode = n1;
var fastNode = n1;

// Check if nextNode is not null and nextNode of the nextNode 
// (2 Nodes from the current Node) is also not null
while(fastNode.nextNode != null && fastNode.nextNode.nextNode != null) {
// slowNode should be moving to the next element of the linked list sequentially
slowNode = slowNode.nextNode;
// Now the fastNode should be twice as faster as the slowNode
fastNode = fastNode.nextNode.nextNode;
}

console.log(slowNode.data);

Relevant Code using Java

public class MiddleElementLinkedList {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		// Create Linked List Nodes
		
		LinkedListNode n5 = new LinkedListNode("5", null);
		LinkedListNode n4 = new LinkedListNode("4", n5);
		LinkedListNode n3 = new LinkedListNode("3", n4);
		LinkedListNode n2 = new LinkedListNode("2", n3);
		LinkedListNode n1 = new LinkedListNode("1", n2);
		
		// Set the starting point
		
		LinkedListNode slowNode = n1;
		LinkedListNode fastNode = n1;
		
		while(fastNode.getNextNode() != null && fastNode.getNextNode().getNextNode() != null){
			slowNode = slowNode.getNextNode();
			fastNode = fastNode.getNextNode().getNextNode();
		}
		
		System.out.println("Middle Element: " + slowNode.getData());

	}
	
	public static class LinkedListNode {
		private String data;
		/**
		 * @return the data
		 */
		public String getData() {
			return data;
		}

		/**
		 * @param data the data to set
		 */
		public void setData(String data) {
			this.data = data;
		}

		/**
		 * @return the nextNode
		 */
		public LinkedListNode getNextNode() {
			return nextNode;
		}

		/**
		 * @param nextNode the nextNode to set
		 */
		public void setNextNode(LinkedListNode nextNode) {
			if(nextNode == null)
				this.nextNode = null;
			this.nextNode = nextNode;
		}

		private LinkedListNode nextNode;
		
		LinkedListNode (String data, LinkedListNode nextNode) {
			this.data = data;
			this.nextNode = nextNode;
		}
	}

}

Here is how the linked list looks in Java

linkedlistjava

 

Happy Coding !!!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s