Advertisement
Guest User

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

a guest
Feb 26th, 2012
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  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]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement