The code is a poor algorithm for reversing a linked list. You presumably have either converted the rest of the class, or have your own linked list class and are just trying to copy the reversal algorithm. You should really include these details and what you've tried when you ask questions on SO, without them people answering can often only guess and you've failed to show any effort - the latter is important.
While this code strongly suggests a linked list there is no clue in this fragment whether this is a single or double-linked list. The code fragment you supply indicates that you have a MyList
class with manages a linked list made up of ListNode
objects.
The basic operations on a linked list are typically:
- Access/change the value stored in the current node - in your code this is the property
head
and it is an object reference of typeListNode
; which itself appears to hold a string. - Access/change the reference to the remainder ("tail") of the list - in your code the
getNext
&setNext
methods.
The method you show RecReverse
is a way to recursively produce a new list which is the reverse of the current list. The algorithm does this by reversing the tail of the list and then appending the head onto the end - using the method end
.
If the list is double-linked and/or keeps a reference to the end of the list then the algorithm is ok - the method end
does not need to traverse the list in this case. Just write it in Objective-C and add it to your list class.
If the list is single-linked and does not keep a reference to the end of the list then the algorithm is poor and the method end
does need to traverse the list. This makes it an O(n^2) algorithm - every step traverses the list.
A better algorithm in this case is to use an accumulating parameter. In pseudo-code this is:
Reverse(l)
if length(l) <= 1
then return l // empty list or list with one element reversed is itself
else return ReverseHelper(l, new empty list)
ReverseHelp(remainder, result)
if remainder is empty
then return result // no more elements left to process
else return ReverseHelp(tail of remainder, add head of remainder to front of result)
Implement that on Objective-C and add it to your linked list class.
HTH