Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Algorithm to Find the pointer to the Node M Steps to Tail in a Singly Linked List

By: a guest on Feb 26th, 2012  |  syntax: None  |  size: 1.33 KB  |  views: 30  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. node* get_Mth_from_end(node* head, int m)
  2. {
  3.   int pos = 0;
  4.   node** node_array = new node*[m + 1];
  5.   node_array[0] = head;
  6.   while (node_array[(pos + 1) % (m + 1)] = node_array[pos % (m + 1)]->next)
  7.      pos++;
  8.   if (pos < m)
  9.   {
  10.      delete[] node_array;
  11.      return NULL;
  12.   }
  13.   pos = pos - m;
  14.   if (pos < 0)
  15.      pos = pos + m + 1;
  16.   node* retval = node_array[pos];
  17.   delete[] node_array;
  18.   return retval;
  19. }
  20.        
  21. int getNumNodesAfter(Node *node){
  22.    if( node->next == NULL ){
  23.       return 0;
  24.    }else{
  25.       return getNumNodesAfter(node->next) + 1;
  26.    }
  27. }
  28.        
  29. for (n=0, front = 0; p[front] != end; ++n, ++p[front]) {
  30.   for (j = 0; j < m; ++j)
  31.     if (n % j = 0)
  32.       ++ front
  33.   front = front % m
  34. }
  35. front = (front-1) % m
  36. for (j = M; j < n-2^m - (n mod 2^m); ++j)
  37.   ++p[front]
  38.        
  39. FindNFromEnd(head, n)
  40.     counter = 0;
  41.     first = head
  42.     firstplusn = head
  43.     while (head.next != null)
  44.         counter++
  45.         head = head.next
  46.  
  47.         if counter == n
  48.             first = firstplusn
  49.             firstplusn = head
  50.             counter = 0
  51.  
  52.      while counter < n
  53.          counter++
  54.          first = first.next
  55.  
  56.      return first
  57.        
  58. 0   1   2   3   4   5   6   7
  59. 1   FNH
  60. 2   FN  H  
  61. 3   FN      H
  62. 1   F           NH
  63. 2   F           N   H
  64. 3   F           N       H
  65. 1   F           N           H
  66. 2               F           N   H
  67. ---
  68. 3                  [F]
clone this paste RAW Paste Data