Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 35

(a)

A circular list with a header node may be reversed by reversing the direction of the pointers in each node. For this, we use three pointers to march through the circular list from left to right. currentNode points to the node whose pointer (link) we are about to reverse; previousNode points to the node on its left; and nextNode points to the node at the right of currentNode. The link in currentNode is changed from nextNode to previousNode. Then previousNode, currentNode, and nextNode are advanced one node to the right. The code for the member method to reverse a circular list with a header node is given below.

public class HeadCircularListWithReverse
       extends HeadCircularList
{
   /** reverse the linear list */
   public void reverse()
   {
      ChainNode previousNode = headerNode,
                currentNode = headerNode.next,
                nextNode;
      lastNode = currentNode;  // will be when we are done

      while (currentNode != headerNode)
      {// change pointer direction
         nextNode = currentNode.next;
         currentNode.next = previousNode;
   
         // move to next node
         previousNode = currentNode;
         currentNode = nextNode;
      }
      currentNode.next = previousNode;
   }
}

(b)

The complexity is linear in the length of the circular list.

(c)

A sample code to test this method is given in the file HeadCircularListWithReverse.java and the output is given in the file HeadCircularListWithReverse.output.

(d)

The nonmember method to reverse a circular list with a header node is given below.

---

public class ReverseHeadCircularList
{
   public static void reverse(HeadCircularList x)
   {
      int sizeMinus1 = x.size() - 1;
      for (int i = 0; i < sizeMinus1; i++)
      {
         // retrieve and remove first element
         Object y = x.remove(0);

         // insert at proper place
         x.add(sizeMinus1 - i, y);
      }
   }
}

---

(e)

Each invocation of remove takes O(1) time, and each invocation add(sizeMinus1 - i, y) takes O(sizeMinus1 - i) time. Therefore, each iteration of the for loop takes O(sizeMinus1 - i) time. The overall complexity is O( (sum from i = 0 to sizeMinus1 - 1) (sizeMinus1 - i) = O(size2).

(f)

The test program and output appear in the files ReverseHeadCircularList.*.