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.

You are not allowed to copy the linked list, but one thing you can do is to create a "new" linked list by changing the next pointers. So, you could find the tail of the linked list and the node before it (if it exists). You set the tail to be the head of a new linked list, then set the next pointer of the node before it to be a null pointer (if applicable), thereby shortening your original linked list. Repeat to find the tail of the shortened linked list and the node before it. You append the new tail to the new linked list, then set the next pointer of the node before it to be a null pointer, thereby shortening the shortened linked list. Repeat until the shortened linked list is empty.

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.

Easy way: Learn about push and pop operations. Then it's just a matter of:

While the list is not empty, pop an item, and push it onto a new list.
Then point the old list back at the new reversed list.

You could initialize p1 and p2, then update p3 in the loop:

• p1 = root;
• if(p1 == NULL) return p1;
• p2 = p1->next;
• if(p2 == NULL) return p1;
• p₁->next=NULL
• while (NULL != (p3 = p2->next)) do
  
  • p₂->next=p₁
  • p₁=p₂
  • p₂=p₃
  
  
• _​p₂->next=p₁
• return p₂ as the head of the reversed list

Quote:

---

Originally Posted by iMalc

Easy way: Learn about push and pop operations. Then it's just a matter of:

While the list is not empty, pop an item, and push it onto a new list.
Then point the old list back at the new reversed list.

---

I suggested this in post #2.