Algorithm to determine if a linked list is circular or has a loop

Problem: how do you find out if a linked list is circular (ie. 1->2->3->4->1) or has a loop (ie. 1->2->3->4->2)?

Understand the problem: a circular linked is like a circle where the end node points to the head node instead of null like in a regular linked list. The example, 1->2->3->4->1, has the end node 4 points to the head node 1, creating a cycle. Similarly, a linked list is said to have a loop when it contains a cycle. However, the cycle doesn't have to start at the head node. It can start at any node in the list. For instance, 1->2->3->4->2 has a loop that starts at node 2 and ends at node 4.

Solution: to solve this problem, we'll have two pointers moving at different speeds over the list. The slow pointer will move through the list one one at a time while the fast pointer will move over two nodes at a time. In other words, the fast pointer will move twice as fast as the slow pointer. When the slow and fast pointer point at the same node, we know that the linked list either is circular or has a loop. But if the linked list is just a regular list, the fast pointer will reach null before the slow pointer.

Algorithm implementation: here is the algorithm implemented in C++

#include<iostream>
using namespace std;

struct Node
{
  int data;
  Node* next;
};

bool hasLoopInList(Node* head)
{
  if (head == NULL)
    return false;

  Node* slow = head;
  Node* fast = head;

  while (fast->next != NULL && fast->next->next != NULL)
  {
    slow = slow->next;
    fast = fast->next->next;

    if (slow == fast)
      return true;
  }

  return false;
}

Code explanation:

1. Check whether the list is empty. If it is, return false because an empty list neither is circular nor has loop.
2. Create two pointers, slow and fast, that are used to traverse the list and determine if the list has loop or not. Initially, these pointers will point at the first node in the list.
3. Next, we just need to loop until our fast pointer reaches null or until the slow and fast pointer points at the same node. If the list is just a regular list, nothing will happen inside the while loop. And, the while loop will end eventually because the fast pointer will reach null. On the other hand, if the list has loop or is circular, the slow and fast pointers will eventually point at the same node. That's why we check for that condition for every iteration of the while loop. And as soon as we know the list has a loop, we return true.

This is a very efficient way to find out if a linked list has loop or is circular. The time complexity is O(n) where n is the number of nodes in the list. Moreover, the space complexity is O(1) because we only need two pointers no matter how long the list we need to check is.

Converting ASCII representation of positive numbers to integer

A number can be represented as ASCII characters (char) or integers (int). Thus, the question is how we can convert from char to int. For example, we want to convert '123' to 123 or '45' to 45.

To solve this problem, we need to revisit the ASCII table for a little bit. Moreover, we are interested in the characters '0' to '9' in the table. The special thing about those characters is that they stand consecutively in the table. That means their decimal values are consecutive positive integers. For example, '0' is 48; '1' is 49; and '2' is 50. Thus, if we have '1' - '0', we'll get an integer value of 1 because 49 - 48 = 1. That's how we're gonna convert the number from char to int. Here is the algorithm in C++:

#include<iostream>
#include<math.h>
using namespace std;

int digitsToInt(char arrayOfChars[], int size)
{
  int digitPos = size - 1;
  int result = 0;
  for (int i = 0; i < size; i++)
  {
    result += ((int)(arrayOfChars[i] - '0')) * pow(10, digitPos);
    digitPos--;
  }
  return result;
}

Explanation: our function takes an array of characters containing the char representation of the number and the size of the array.

1. digitPos keeps track of which digit we're converting. It is important to do so because we must convert the digit into appropriate value in integer (remember that ASCII digits are between '0' and '9'). If the number passed in is '102', then the first digit '1' represents 100 in integer. The algorithm must know that and multiply '1' with 100 after converting it into int 1.
2. result is the final number in int. Our strategy here is to convert each digit into its appropriate int value and then add all of them up. That will give us the final result in integer. For example, if we need to convert '12', we will convert '1' to 1 first and multiply it by 10. Next, we convert '2' to 2 and multiply it by 1 (2 is the last digit). Therefore, the final result is 10 + 2 = 12.
3. We loops through the array and convert each digit into the appropriate int value and add that value into the result. As explained above, by subtracting the digit by '0' and casting the result into int we'll get the correct int number corresponding to that digit. However, that's not all. Notice how we use the function pow(10, digitPos) to get the correct value for each digit. This method works because our numbers are base 10 numbers. Thus, by multiplying a number by 10 to the power of its position, we'll get the correct value for that number. Don't worry if you are confused, we'll do an example later.
4. Lastly, we decrement digitPos by one because we will move to process the next digit which has one order less than the current number.
5. Return the final result which is the sum of all the int values of our digits.

Example: we'll convert the number '123' into integer.

1. Our digitPos is 2 because we process the first digit '1' first and it is in the hundredth position. So, '1' - '0' gives int 1. Then, 1 * 10 ^ 2 = 100. Add that into our result. We have 100 after the first iteration. Moreover, digitPos decreases by 1 because we are about to process the tenth digit.
2. Second iteration, digitPos is 1. And we have '2' - '0' = int 2. Multiplying 2 by ten to the power of its position, we have 2 * 10 ^ 1 = 20. Add that value to the result and we end up with the sum of 120. Finally, we decrement digitPos by 1.
3. Last iteration, digitPos is 0. And, '3' - '0' = int 3. Multiplying 3 by ten to the power of its position, we have 3 * 10 ^ 0 = 3. Add 3 into the result and we have int 123. Loop ends and our algorithm returns the result of 123.

Thanks for reading and as always feel free to leave any comment or suggestion :)