Chapter 3: Linked Lists – 8. Problems & Solutions (11-20)

Problem-11

We are given a pointer to the first element of a linked list L. There are two possibilities for L, it ends up (snake) or its last element points to one of the the previous element in the list (the snail). Give an algorithm that checks whether a given list L is a snake or a snail.

Solution : It is the same as Problem-7.

Problem-12

Checks if the given linked list is NULL terminated. If there is a cycle, find the start node of the loop.

Solution :
The solution is an extension to the solution in Problem-10. After finding the loop in the linked list, we initialize slowPtr to the top of the linked list. From that point on, both slowPtr and fastPtr move only one node at a time. The point where they meet is the starting point of the loop.
Generally, we use this method to eliminate loops. Let x and y be travelers such that y goes twice as fast as x (i.e. y = 2x). Let s be where x and y first meet and start walking at the same time.
Then, when x and y meet again the next time, the distance from s to the start of the loop is exactly equal to the distance from the current meeting point of x and y to the beginning of the loop.

Problem-13

Prove that the above algorithm is correct.

Solution : This problem is central to number theory.
In the Floyd cycle finding algorithm, note that the tortoise and the hare will meet when they are of size n × L, where L is the loop length. Furthermore, the tortoise is in the midpoint between the hare and the beginning of the chain because of the way they move. Therefore, the turtle is also n × L from the beginning of the sequence.
If we move both steps at a time, from the position of the turtle and from the beginning of the sequence, we know that they will meet as soon as both are in the loop, since they are n × L, a multiple of the loop length, spaced.
One of them is already in the loop, so we just move the other in a single step until it enters the loop, keeping the other n × L away from it all the time.

This explanation is really a bit confusing, I also find it difficult to understand, so I have a reference here , or if you want to watch a vivid video, here

Put
X = Distance between the start (start) to the start of the loop.
Y = Distance between the start of the loop and the first meeting point of both pointers.
C = Loop length

When 2 pointers meet for the first time:

• The slow pointer has traveled the distance
  X + Y + S OLD X + Y + s * SIZE$X+Y+s\_C$ , where s is any positive constant.
• The fast pointer has covered the distance
  X + Y + f OLD X + Y + f * L$X+Y+f\_C$ , where f is any positive constant.

Since the fast pointer is twice as fast as the slow pointer, the time the fast pointer meets will be twice as long as the slow pointer.
=>

X + Y + f OLD = 2 ( X + Y + S OLD ) X + Y + f * C = 2 * (X + Y + s * C)$X+Y+f\_C=2\_(X+Y+s\_C)$

$X$$+$$Y$$=$$f$$OLD$ $–$ $2$$S$$OLD$ $X\; +\; Y\; =\; f\; *\; C\; –\; 2\; *\; s\; *\; C$$X+Y=f\_C-2\_s\_OLD$

$f$$OLD$ $–$ $2$$S$$OLD$$=$ $($$S$$o$$m$$e$$i$$n$$t$$e$$g$$e$$r$ $)$$OLD$$=$$KY$$OLD$ $f\; *\; C\; –\; 2\; *\; s\; *\; C\; =\; (some\; integer)\; *\; C\; =\; K\; *\; C$f _ C -2 s C = (so m e in t e g er ) C = K OLD

So we get:

X + Y = KY OLD X + Y = K * C$X+Y=K\_C$ – ( 1 )

$X$ $=$ $KY$ $OLD$ $–$ $Y$ $X\; =\; K\; *\; C\; –\; Y$X = K _ C – Y – ( 2 )
Where K is any positive constant

• Now if we reset the slow cursor to the beginning (start position) and move the cursor fast and slow one by one, one can observe from the first and second equations that the two will meet later when traveling X distance at loop start point because after resetting slow pointer and moving it distance X, also from loop meet point fast pointer will also move distance
  KY OLD − Y K * C – Y$K\_C-Y$ (because it has traveled the distance Y).
• From equation (2), we have
  X = KY OLD − Y X = K * C – Y$X=K\_C-Y$ , so both pointers will travel X distance i.e. the same distance to meet at the start of the cycle.

Problem-15

Checks if the given linked list is NULL terminated. If there is a cycle, find the length of the loop.

Solution : This solution is also an extension of the basic cycle detection problem.
Once the loop is found in the linked list, keep slowPtr as it is.
FastPtr keeps moving until it goes back to slowPtr.
Now the fastPtr pointer moves step by step.

Time Complexity: O(n).
Space Complexity: O(1).

Problem-16

Insert a node into a sorted linked list

Solution : Browse through the list and find the right position and insert.

Time Complexity: O(n).
Space Complexity: O(1).

Problem-17

Reverse a singly linked list.

Solution :
Iterative version:

Time Complexity: O(n).
Space Complexity: O(1).

Recursive version:

Time Complexity: O(n).
Space Complexity: O(n), used for stack recursion

Problem-18

Assume there are two singly linked lists, both of which intersect at some point and become a single linked list. The head pointer or the start pointer of both lists is known, but the intersection is not known.
In addition, the number of nodes in each list before they intersect is unknown and may vary in each list. List1 can have n nodes before it reaches the intersection and List2 can have m nodes before it reaches the intersection where m and n can be

m = n , m < n m = n, m < n$m=n,m<n$ or

$m$ $>$ $n$ $m\; >\; n$m > n .
Provide an algorithm to find the merge point.

Solution : Brute-Force Approach
A simple solution is to compare every node pointer in the first list with every other node pointer in the second list whereby matching node pointers will lead us to the intersection.
However, the time complexity in this case would be

O ( m n ) O (mn)$O(m)$ will be high.

Time Complexity:

O ( m n ) O(mn)$O(m)$ .
Space Complexity:

O ( first ) O(1)$O(1)$

Problem-19

Can we solve Problem-18 using sorting technique?

Solution :No. Consider the following algorithm based on sorting and see why it fails.
Algorithm :

• Take the first list node pointers and keep them in some array and sort them.
• Take the second list node pointers and keep them in some array and sort them.
• After sorting, use two indexes: one for the first sorted array and one for the second sorted array.
• Start comparing values ​​at the indexes and increment the index according to the lower value (increment only if the values ​​are not equal).
• At any given time, if we can find two indexes with the same value, that indicates that the two nodes are pointing to the same node and we return that node.

Time Complexity: List sort time + Scan time (for comparison)

= O ( m l o g m ) + O ( n l o g n ) + O ( m + n ) = O(mlogm) + O(nlogn) + O(m + n)$=O(mlogm)+O(nlogn)+O(m+n)$
We need to consider the one that gives the greatest value.
Space Complexity:

$O$ $($$first$ $)$ $O(1)$O ( 1 ) .

Is there any problem with the above algorithm? Yes. In the algorithm, we are storing all the lists and sorting them. But we are forgetting the fact that there can be many repeating elements . This is because after the merge point, all node pointers are the same for both lists. The algorithm works well only in one case and that’s when both lists have an end node at their merge point.

Problem-20

Can we solve Problem-18 using hash tables?

Solution : Yes.
Algorithm :

• Choose a list with less number of nodes (If we don’t know the length in advance, let’s randomly choose a list).
• Now traverse another list and for each node pointer of this list check if the same node pointer exists in the hash table.
• If there is a merge point for the given lists then we will surely meet in the hash table.

Time Complexity: Hash table creation time + Second list scan time =

O ( m ) + O ( n ) O(m) + O(n)$O(m)+O(n)$ (or

$O$ $($ $n$ $)$ $+$ $O$ $($ $m$ $)$ $O(n)\; +\; O(m)$O ( n ) + O ( m ) , depending on the list we choose to create the hash table. Space Complexity:

$O$ $($ $n$ $)$ $O(n)$O ( n ) or

$O$ $($ $m$ $)$ $Braised)$O ( m ) .