Necessary and Sufficient

Question: Write a function to reverse an array in-place in C#.
Answer: Since arrays have direct access via the [] operator it's simple enough to iterate through the array elements and perform a swap. The key things to remember are: (1) you only need to iterate over half of the array; and (2) it's best to write this as a generic function since we make the function more useful.

Note that arrays are reference types in C# so it doesn't matter if you pass the array in by reference or by value, the outcome will be the same if the array is not initially null.

Here's the C# code:

        static void Main()
        {
            var arr = new byte[] {0x04, 0x01, 0x02, 0x06, 0x00};
            ReverseArray(arr);
            foreach(var element in arr)
                Console.WriteLine( element );
        }

        public static void ReverseArray<T>(T[] a)
        {
            int n = a.Length;
            for (int i = 0; i < n/2; i++)
            {
                T t = a[n-i-1];
                a[n-i-1] = a[i];
                a[i] = t;
            }
        }

Problem: You have a singularly-linked list that has a cycle in it. Define an algorithm that proves that the list has a cycle. Your algorithm must have linear time complexity and cannot mark the list items.

Solution: A linked list with a cycle in it means that when you start traversing the list you will eventually retrace your steps and enter an infinite loop.

One way to detect a cycle is by keeping track of nodes already visited in the list, but the question prohibits us from marking the elements or using an additional data structure. In fact, even if the question allowed us to use an alternate data structure it would not be efficient to have to search an auxiliary "visited" list on each node.

Another way to detect the cycle is to use 2 pointers - one that advances one step at a time and one that advances 2 steps at a time. If either pointer runs into a NULL node then we know the list does not have a cycle. And because the faster pointer steps ahead 2 nodes at a time it will eventually catch/overtake the slower pointer. We can use this fact to detect the loop and break out of the infinite loop.

This technique is known as Floyd's cycle-finding algorithm, or the "tortoise and hare" algorithm. It has linear run time complexity and constant space complexity.

Here's my C++ code to do it.

   1:  #include <stdio.h>

   2:  #include <stdafx.h>

   3:  #include <malloc.h>

   4:   

   5:  struct node{

   6:      int data;

   7:      node* next;

   8:  };

   9:   

  10:  void push(node** head, int data){

  11:      node* newNode = new node;    // struct keyword not necessary in C++

  12:      newNode->data = data;

  13:      newNode->next = *head;

  14:      *head = newNode;

  15:  }

  16:   

  17:  bool detectCycle(node* head){

  18:      node* fast = head;

  19:      node* slow = head;

  20:   

  21:      do{

  22:          if (fast->next == NULL || fast->next->next == NULL)

  23:              return false;

  24:   

  25:          fast = fast->next->next;

  26:          slow = slow->next;

  27:      } while(fast != slow);

  28:      return true;

  29:  }

  30:   

  31:  int main(){

  32:      

  33:      node* head= NULL;        

  34:      for(int i=7; i>=1;i--){

  35:          push(&head, i);

  36:      }

  37:      

  38:      // close the list

  39:      node* last = head;

  40:      while(last->next != NULL){

  41:          last = last->next;

  42:      }

  43:      last->next = head;

  44:   

  45:      bool hasCycle = detectCycle(head);

  46:      printf("hasCycle= %d\n",hasCycle);

  47:  }

Question: Write a C++ function that takes a singularly-linked list and recursively reverses it. It must have linear, O(n), run time - that is you are only allowed to make 1 pass through the list. No changes to the list data can be made and no additional data structures can be used.

This is very similar to the non-recursive linked list reverse problem.

Solution: My approach to this problem is to use the recursion to drill into the list and to do the pointer swapping on the way back up the recursive call stack. In lines 18-28 below we call the function recursively until we have reached the end of the linked list which is determined by the NULL node pointer checks. Lines 30-32 do not get called until we have gotten to the end of the linked list and we are on our way back up the call stack. These lines merely set the "next" pointer for the current element to point to the previous element, and remove the "next" pointer on the current pointer. The head of the list is then updated.

Here's my C++ code to do this:

   1:  #include <stdio.h>

   2:  #include <stdafx.h>

   3:  #include <malloc.h>

   4:   

   5:  struct node{

   6:      int data;

   7:      node* next;

   8:  };

   9:   

  10:  void push(node** head, int data){

  11:      node* newNode = new node;    // struct keyword not necessary in C++

  12:      newNode->data = data;

  13:      newNode->next = *head;

  14:      *head = newNode;

  15:  }

  16:   

  17:  void recursiveReverse(node** start){

  18:      node* current = *start;

  19:      

  20:      if (current == NULL)

  21:          return;

  22:   

  23:      node* rest = current->next;

  24:      

  25:      if (rest == NULL)

  26:          return;

  27:   

  28:      recursiveReverse(&rest);

  29:   

  30:      current->next->next = current;

  31:      current->next=NULL;

  32:      *start=rest;

  33:  }

  34:   

  35:  int main(){

  36:      

  37:      node* head= NULL;    

  38:          

  39:      for(int i=7; i>=1;i--){

  40:          push(&head, i);

  41:      }

  42:      

  43:      node* current = head;

  44:      while(current != NULL){

  45:          printf("%d ",current->data);

  46:          current = current->next;

  47:      }

  48:   

  49:      recursiveReverse(&head);

  50:      printf("\n");

  51:   

  52:      current = head;

  53:      while(current != NULL){

  54:          printf("%d ",current->data);

  55:          current = current->next;

  56:      }

  57:  }