Linked list recursive reverse

by

Draw out a stack trace…

Intial - {1,2,3,4}
Head - 1
Rest = 2,3,4
Recurse(2,3,4)
Head = 2
Rest = 3,4
Recurse(3,4)
Head = 3 
Rest = 4
Recurse (4)
Head = 4
Rest = null //Base Case Reached!! Unwind.

So now we pick up 
Recurse(3,4)
Head = 3 
Rest = 4
// Return picks up here
first->next->next  = first; 
so list is:
3,4,3
// set head to null,
null ,4,3,
//Off with his head!
4,3
Return

Now we're here
Recurse(2,3,4)
Head = 2
Rest = 3,4
Previous return leaves state as:
Head = 2  //But Head -> next is still 3! -- We haven't changed that yet..
Rest = 4,3  
Head->next is 3, 
Head->next->next = 2 makes the list (actually a tree now)
4->3->2
   ^
   |
   2
And chop off the head leaving
4->3->2
and return.

Similarly, do the last step which will leave
4->3->2->1
      ^
      |
      1
and chop off the head, which removes the one.

More Related Contents:

  1. Recursive C function
  2. How to reverse a singly linked list using only two pointers?
  3. Power by squaring for negative exponents
  4. Finding the intersecting node from two intersecting linked lists
  5. Merging two sorted linked lists
  6. How to generate numbers upto 18 digits, sum of whose reciprocals is a whole number [closed]
  7. Why this C code makes infinite loop?
  8. The most efficient way to implement an integer based power function pow(int, int)
  9. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  10. What integer hash function are good that accepts an integer hash key?
  11. Unique random number generation in an integer array [duplicate]
  12. Calculating factorial of large numbers in C
  13. How to recursively list directories in C on Linux?
  14. Combine Gyroscope and Accelerometer Data
  15. Using pointers to remove item from singly-linked list
  16. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  17. C How to “draw” a Binary Tree to the console [closed]
  18. Segmentation Fault when writing to a string [duplicate]
  19. How to do unsigned saturating addition in C?
  20. Traverse Matrix in Diagonal strips
  21. unexpected output in C (recursion)
  22. Rationale behind the container_of macro in linux/list.h
  23. Rolling median in C – Turlach implementation
  24. Segmentation fault occurring when modifying a string using pointers?
  25. Find maximum of three number in C without using conditional statement and ternary operator
  26. Algorithm to find all the exact divisors of a given integer
  27. Which is better way to calculate nCr
  28. Creating N nested for-loops
  29. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  30. Infinite recursion in C

Leave a Comment