Damien Wintour’s personal musings on technology, mathematics, startups and leadership.

Uncategorized

Loop Detection in Linked Lists

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:  }

04 May 2008 Damien Wintour 0 comments

Uncategorized

Recursively Reverse a Linked List

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:  }

03 May 2008 Damien Wintour 1 comment

Uncategorized

Reverse a Linked List

Question: Write a C++ function that takes a singularly-linked list and 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 similar to the recursive reverse problem.

Solution: This is an exercise in pointer manipulation and understanding the difference between pass by value and pass by reference. All we need to do is to traverse the list keeping a reference/pointer to the last node visited and for the current node tweak the "next" pointer to point to the last node. Of course, before we overwrite the "next" pointer we need to take a copy of it first, otherwise we wouldn't be able to continue the list traversal. The hidden danger in this problem is making sure the head pointer is accurate at the end of the list traversal.

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 reverse(node** head){
  18:      node* current = *head;
  19:      node* last = NULL;
  20:      node* oldNext = current;
  21:   
  22:      while (current != NULL){
  23:          oldNext = current->next;
  24:          current->next = last;
  25:          last = current;
  26:          current = oldNext;
  27:      }
  28:      *head=last;
  29:  }
  30:   
  31:  int main(){
  32:      
  33:      node* head= NULL;    
  34:          
  35:      for(int i=7; i>=1;i--){
  36:          push(&head, i);
  37:      }
  38:      
  39:      node* current = head;
  40:      while(current != NULL)
  41:      {
  42:          printf("%d ",current->data);
  43:          current = current->next;
  44:      }
  45:   
  46:      reverse(&head);
  47:      printf("\n");
  48:   
  49:      current = head;
  50:      while(current != NULL)
  51:      {
  52:          printf("%d ",current->data);
  53:          current = current->next;
  54:      }
  55:  }

In the code above we use 3 node pointers (in lines 18-20) to keep track of the current node and the one before and after it. Along these same lines there is an alternative approach to the reverse problem that employs 3 iterators, called back, middle, front which effectively does the same thing as the algorithm above. For completeness, here is the 3-iterators approach:

   1:  // the three-pointer approach
   2:  void reverse2(node** head){
   3:      if (*head != NULL){
   4:          node* middle=*head;
   5:          node* front =middle->next;
   6:          node* back=NULL;
   7:          
   8:          while(true){
   9:              middle->next = back;    // reverse the middle node
  10:              
  11:              // move all pointers forward
  12:              if (front == NULL)
  13:                  break;
  14:   
  15:              back = middle;
  16:              middle = front; 
  17:              front = front->next;
  18:          }
  19:          *head = middle;
  20:      }
  21:  }

02 May 2008 Damien Wintour 1 comment

« Prev - Next »