Skip to content

Data Structure Strategies

List Strategies

Find midpoint of a list without using size or counter variables?

Take 2 variables (slow and fast). Run a loop on the list till fast reaches the end of the list. While slow increments with 1, fast increments with 2. this way we can find the midpoint.

Find Circular Reference in a loop?

The above technique fast and slow can be extended to solve this problem. As the loop never terminates so checking if fast and slow or equal will let us know whether its a circular reference or not

From Last return nth Element?

without using length or size you need to return nth element so to solve this problem you have to use again the same 2 pointer technique. Now make sure the difference b/w pointers is n index. then run the loop the fast pointer reaches null and the slow will give solution.

Sample Program:

function midpoint(list) {

/* 	let node = list.head;
	if(!node.next || !node.next.next){
		return node;
	}

	let slow = node.next;
	let fast = node.next.next;

	while(fast.next && fast.next.next)
	{
		
		fast = fast.next.next;
		slow = slow.next;		
	}
	
	return slow; */
	
	let slow = list.getFirst();
	let fast = list.getFirst();
	
	while(fast.next && fast.next.next){
		slow = slow.next;
		fast = fast.next.next;
	}
	
	return slow;
  
}
function circular(list) {
	let slow = list.getFirst();
	let fast = list.getFirst();
	
	while(fast.next && fast.next.next){
		slow = slow.next;
		fast = fast.next.next;
		if(slow === fast){
			return true;
		}
	}
	
	return false;
}
function fromLast(list, n) {	
	let pointer1slow = list.getFirst();
	let pointer2fast = list.getFirst();
	
	while(n>0){
		pointer2fast = pointer2fast.next;
		n--;
	}
			
	while(pointer2fast.next){
		pointer2fast = pointer2fast.next;
		pointer1slow = pointer1slow.next;
	}
	
	return pointer1slow;
		
}
Published inUncategorised

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *