Thread: How to reverse a unidirectional linked list

Hi.
I was assigned to reverse a unidirectional linked list in C, where I'm not allowed to make a copy of the given linked list, or to change the actual data.
The only thing I'm allowed to do is to manipulate the list's pointers.
After doing some thinking and scribbling on a piece of paper, I came up with this:

• Initialize three pointers: p₁,p₂,p₃, for the first, second and third elements, respectively.
• p₁->next=NULL
• while (p₃ != NULL) do
  
  • p₂->next=p₁
  • p₁=p₂
  • p₂=p₃
  • p₃=p₃->next
  
  
• p₂->next=p₁
• return p₂ as the head of the reversed list

This is a pseudo code, of course, as I'm less interested in the actual implementation, and more about the algorithm itself.
I was wondering if there's a more elegant way of doing this, since this gets quite complicated considering the cases where the list has less than three elements in it.

I'll start with your original implementation. The cases for fewer than 3 elements are not complex, but rather fairly trivial. Draw it out on paper if you need to. The case for zero- and one-element lists is ridiculously easy. The case for a two-element list isn't that difficult (mine is 4 lines). All you would have to do is

Code:

if zero or one elements
    // super trivial
else if two elements
    // less trivial, but still trivial
else
    your algorithm

Analyze your algorithm carefully, it may work for two-element lists, leaving you with only the trivial zero-/one-element list case. Again, draw it out on paper if you need to.

There is a recursive solution which, while not the most elegant, took me 5 lines and used 1 temp variable. You can run into trouble with extremely large lists, however, as you may run out of stack space with all those recursive calls.

Of course, as laserlight mentioned, you can create a "new" list. Her solution works, however, I find it easier to work from the head of the list. Sometimes, to find these types of solutions, it helps to think about this in a more abstract manner. Forget that you have to explicitly manipulate the next pointer of the nodes, and instead focus on operations that apply to the list regardless of implementation. For example, you can add nodes by prepending (add at beginning), appending (add at end) and inserting in the middle. Also, you can remove nodes from the beginning, middle and end. Now, what operations can you use to extract nodes from the old list, and insert them into the new list, such that your new list is the reversal of your old list.