Zeyuan Hu's page

Reverse Singly Linked List

Problem

This problem is MAW 3.12:

  1. Write a nonrecursive procedure to reverse a singly linked list in O(N) time.
  2. 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].

comments powered by Disqus