Addition in Linked List

Problem Statement

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Continue reading

Loop in Linked List

Hi to all,

This is my first article in this blog. The article briefly describes How to Find a Loop in Linked List and Finding the start of the Loop.

To find the Loop in linked list, we can use Floyd’s Cycle Detection Algorithm. The algorithm is also Tortoise – Hare Algorithm. 

Concepts Behind Floyd’s:

Imagine a circular track and two runners. One runner is twice as fast as the other. Both of them start at same point  ‘P’. The only point they will meet in the circular track again is the start point ‘P’.

If the slow runner starts at “S” and fast runner starts at “K” distance away from the point “S”, then they will meet in the circular track at “K” distance before the start point “S”.

See this diagram for clear understanding,

first

The fast runner ‘F’ is quarter distance ahead of ‘S’.  ‘S’ is the starting point. They both meet quarter distance before the starting point ‘S’.

The point we derive from this is :

If  the faster runner is ‘K’ step ahead of the slow runner at the start of the race, then they meet first at ‘K’ Steps before the starting point.

You can have a better understanding , if u are able to crack this spoj problem .

Continue reading