Chapter 3: Linked Lists – 8. Problems & Solutions (1-10)

Problem-1

Deploy a Stack using Linked List

Solution : I will explain in detail when I write to the Stacks chapter

Problem-2

Find the nth node from the end of the Linked List

Solution :
Simply we can use Brute-Force Method:
Start with the first node and count the number of nodes present after that node. If the number of buttons

< n − first < n – 1$<n–1$ then returns the message “the number of nodes in the list is less than the number to find”.
If the number of buttons

$>$ $n$ $-$ $first$ $>\; n\; –\; 1$> n – 1 then moves to the next node. Continue this until the number of nodes after the current node to the last node is

$n$$-$$first$ $n\; –\; 1$n – 1 .

Time complexity:

O ( n 2 ) O(n^2)$O(n^2)$ , to scan the remaining list (from the current node) for each node.
Spatial Complexity:

$O$ $($ $first$ $)$ $O\; (1)$O ( 1 ) .

Problem-3

Can we improve the complexity of Problem-2?

Solution :
Yes, using hash table. For example, consider the following list:

In this approach, create a hash table whose entries are <node location, node address>.
That is to say, key is the position of the node in the list and value is the address of that node.

By the time we traverse the entire list (to create a hash table), we have the length of the list.
Assume the length of the list is M. To find the nth node from the end of the linked list, we can convert it to finding the nth position.

USA − n + first M – n + 1$M-n+1$ from the beginning of the list.
Since we already know the length of the list, it’s just a matter of returning the th key value

$USA$ $-$ $n$ $+$ $first$ $M\; –\; n\; +\; 1$M − n + 1 from the hash table. Time Complexity: Time to generate hash table,

$BILLION$ $($$m$ $)$$=$$O$ $($$m$ $)$ $T(m)\; =\; O(m)$T ( m ) = O ( m ) .
Space Complexity: we need to create a hash table of size m,

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

Problem-4

Can we use Problem-3 approach to solve Problem-2 without creating hash table?

Solution :
Have.
If we look at the solution to Problem-3, what we’re really doing is finding the size of the linked list.
That means we are using a hash table to find the size of the linked list.
We can find the length of the linked list just by traversing the list from the top node. So we can get the length without creating a hash table.
After finding the length, calculate

USA − n + first M – n + 1$M-n+1$ and with one more traversal we can get the th node

$USA$ $-$ $n$ $+$ $first$ $M\; –\; n\; +\; 1$M − n + 1 from the very beginning.
This solution requires two traversals: one to find the length of the list, and one to find the Mth node – n + 1 from the beginning.

Time Complexity: Time to find the length + Time to find the th node

USA − n + first M – n + 1$M-n+1$ from the beginning. Therefore,

$BILLION$ $($ $n$ $)$ $=$ $O$ $($ $n$ $)$ $+$ $O$ $($ $n$ $)$ $O$ $($ $n$ $)$ $T(n)\; =\; O(n)\; +\; O(n)\; O(n)$T ( n ) = O ( n ) + O ( n ) _ O ( n ) .
Space Complexity:

$O$ $($$first$ $)$ $O\; (1)$O ( 1 ) . Because there is no need to create a hash table.

Problem-5

Can we solve Problem-2 in one scan?

Solution :
Yes. Efficient Approach
Use two pointers pNthNode and pTemp.
Initially, both point to the top node of the list.
pNthNode starts migrating only after pTemp has made n migrations.
From there both move forward until pTemp reaches the end of the list.
As a result, pNthNode points to the nth node from the end of the linked list.

Note : At any given time, both move one button at a time.

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

Problem-6

Can we solve Problem-5 with recursion?

Solution :
Yes, we can use a global variable in a recursive function and return it when the value is equal to n.

Time Complexity: O(n) for pre-recursive calls and O(n) for post-recursive calls, is

O ( 2 n ) = O ( n ) O(n) = O(n)$O(2n)=O(n)$ .
Space Complexity: O(n) for the recursive stack.

Problem-7

Check if given linked list is NULL terminated or cycle terminated (in cycles)

Solution :
Brute-Force Approach
For example, consider the following linked list with a loop in it. The difference between this list and the regular list is that, in this list, there are two nodes with the same next pointer.
In a regular singly linked list (without loops), each node’s subsequent pointer is unique. That means the subsequent iteration of pointers indicates the existence of a loop.

A simple and crude way to solve this is to start with the first node and see if any node has the next pointer which is the address of the current node.
If there is a node with the same address it indicates that some other node is pointing to the current node and we can say that a loop exists.
Continue this process for all nodes of the linked list.

Is this method effective?
Algorithmically we are checking the next pointer addresses, but how do we find the end of the linked list (otherwise we will end up in an infinite loop)?

Note : If we start with a button in the loop, this method may work depending on the size of the loop.

Problem-8

Can we use hashing technique to solve Problem-7?

Solution : Yes, using Hash Tables can solve this problem.
Algorithm :

• Iterate through the list of nodes one by one.
• Check if the node’s address is in the hash table.
• If it is already in the hash table, that shows that we are accessing the already visited node. This is only possible if the given linked list has a loop in it.
• If the node’s address is not in the hash table, insert the node’s address into the hash table.
• Continue this process until we reach the end of the linked list or we find the loop.

Time Complexity: O(n) to traverse the list.
Space Complexity: O(n) for hash table.

Problem-9

Can we solve Problem-7 using Sort?
Solution :
No . Consider the following algorithm based on sorting. Then we see why this algorithm fails.

Algorithm:

• Traverse the linked list nodes in turn and get all subsequent pointer values ​​into an array.
• Sort the array with the next node pointers.
• If there is a loop in the linked list, surely the next two node pointers will point to the same node.
• After sorting if there is a loop in the list, nodes with the same next pointer will end up contiguous in the sorted list.
• If any such pair exists in the sorted list then we say that the linked list has a loop in it.

Time Complexity: O(nlogn) for sorting arrays Space Complexity: O(n) for n-element arrays.

Problem with this algorithm: The above algorithm only works if we can find the length of the list. But if the list has a loop then we can end up with an infinite loop. For this reason the algorithm fails.

Problem-10

We can solve Problem-7 in

O ( n ) O(n)$O(n)$ not?

Solution :
Yes. Efficient Approach (Memoryless Approach):
This issue was resolved by Floyd. The solution is named Floyd cycle finding algorithm. It uses two pointers moving at different speeds to view the linked list. When both enter the loop, they are expected to meet, which indicates that there is a loop.

This works because the only way a faster moving pointer will point to the same place as a slower moving pointer is if somehow the entire list or part of it is circular. Think of a tortoise and a hare running on a track. The faster rabbit will catch up to the turtle if they run around.

Consider the following example and figure out Floyd’s algorithm. From the diagram below, we can see that after the last step, they meet at some point in the loop that might not be the start of the loop.

Note: slowPtr (turtle) moves one step at a time and fastPtr (rabbit) moves two steps at a time.

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