## Problem

This problem is MAW 3.12:

- Write a nonrecursive procedure to reverse a singly linked list in O(N) time.
- Write a procedure to reverse a singly linked list in O(N) time using constant extra space.

## Solution

Essentially, this is just one problem: reverse a singly linked list with various constraints. There are a couple of ways doing so. All of them satisfy 3.12.a and 3.12.b

Note

Solution 2 & 3 are probably most people will expect, particularly during an interview.

### Solution 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | ```
List
reverseList(List L)
{
Pos dummyL = L->Next;
List R = malloc(sizeof(struct Node));
while (dummyL != NULL)
{
Pos tmpNode = malloc(sizeof(struct Node));
tmpNode->Element = dummyL->Element;
tmpNode->Next = R->Next;
R->Next = tmpNode;
dummyL = dummyL->Next;
}
return R;
}
``` |

Solution 1 is pretty straightforward. We first create a new list. Then, we walk through the original list and insert node we visit at the very beginning of the new list. Once we finish the traversal of the original list, we return the new list.

Note

You can use a stack to reverse the list. This will require O(N) extra space.

This solution shows one of the reasons why we use a *header* node or *dummy* node
in our linked list implementation (instead of just use a pointer directly pointing
towards the first element in the list):

Without the dummy node, there is no really obvious way to insert at the front of the list.

This can be seen from Line[12]. Also, this routine has a return type `List` instead of
`void`.

Note

The definition for using or not using *dummy* node is the same. However,
implementation difference can be seen by observing how the program construct
a list: in my case, initializeList.

However, this solution wastes a ton of memory space and too many `malloc` operations,
which basically duplicate the data. This is the place where the algorithm can be improved.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | ```
List
reverseList(List L)
{
Pos dummyL = L->Next;
List R = malloc(sizeof(struct Node));
while (dummyL != NULL)
{
// Remove element from old list.
Pos tmpNode = dummyL;
dummyL = dummyL->Next;
// Insert element in new list.
tmpNode->Next = R->Next;
R->Next = tmpNode;
}
return R;
}
``` |

Note

This solution has two interesting points:

- It's obvious that it's correct: there are no corner cases to worry about and both two-line operations are familiar to anyone who's manipulated a linked list.
- It's pretty much identical to the Solution 2 (same number of temporary variables, same assignments in slightly different order).

### Solution 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | ```
void
reverseListIterative(List L)
{
Pos dummyCurrent = L->Next,
dummyPrev = NULL,
dummyNext;
while (dummyCurrent != NULL)
{
dummyNext = dummyCurrent->Next;
dummyCurrent->Next = dummyPrev;
dummyPrev = dummyCurrent;
dummyCurrent = dummyNext;
}
L->Next = dummyPrev;
}
``` |

The 2nd solution is an iterative approach. The logic itself is quite straightforward.
But, please always remember we assume *dummy* node exists. You can see both from
Line[4] and Line[15].

Note

This actually not the solution I come up initially. My initial implementation works but is not as nice as this one. You can check it out in my linkedList.c

### Solution 3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | ```
static List P;
static void
reverseListRecursiveHelper(List L)
{
if (L->Next == NULL)
{
P = L;
return;
}
reverseListRecursiveHelper(L->Next);
L->Next->Next = L;
L->Next = NULL;
}
void
reverseListRecursive(List L)
{
reverseListRecursiveHelper(L->Next);
L->Next = P;
}
``` |

This solution is a recursive solution. This causes me much time to think about
because we have a *dummy* node to be taken care of. That's why I use a private
helper function. There is a couple important points to be noticed here:

Use a static List variable

`P`is necessary because we need to keep track of where is our first node after reverse (i.e. the last node in the original list will become the first node after reversal). This is important because without`P`, we cannot access the first node because all the links are reversed and we can no longer traverse the list from our*dummy*node.Inside

`reverseListRecursiveHelper`, I don't have to check if`L`is`NULL`(You need to do this for no*dummy*node implementation style). Essentially, this is the base case where I got passed in an empty list. Since in our implementation,*dummy*node always exists even when the list is empty (check out`deleteList`routine),`L->Next`is always valid (we don't want to reference`L`, which is`NULL`already).We use a private function mainly because we have

*dummy*node in our implementation. This is a special case that cannot be handled inside the recusive call. That's also why the first data node in the original list is passed into the helper function.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

List P; void reverseListRecursive(List L) { // empty list base case if (L->Next == NULL) { return; } // only one node (tail node) base case if (L->Next->Next == NULL) { P = L->Next; return; } reverseListRecursive(L->Next->Next); L->Next->Next->Next = L->Next; L->Next->Next = NULL; L->Next = P; }

The above code shows a perfect example why

*dummy*node case cannot be handled in recursive call. This is because, when we do recursion, we always assume there is*dummy*node exists in the sub list we passed in. However, that is not what our list acutally is. You can see why our recursion assumes the*dummy*node exists by reading Line[6] & Line[11] & Line[16].