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

(a)

A chain may be reversed by reversing the direction of the pointers in each node. For this, we use three pointers to march through the chain from left to right. currentNode points to the node whose pointer (link) we are about to reverse; lastNode points to the node on its left (lastNode is null in case currentNode is the first node); and nextNode points to the node at the right of currentNode (nextNode is null in case currentNode is the last node of the chain). The link in currentNode is changed from nextNode to lastNode. Then lastNode, currentNode, and nextNode are advanced one node to the right. The code to reverse a chain is given below.

---

public void reverse()
{
   ChainNode lastNode = null,
             currentNode = firstNode,
             nextNode;

   while (currentNode != null)
   {
      // change pointer direction
      nextNode = currentNode.next;
      currentNode.next = lastNode;

      // move to next node
      lastNode = currentNode;
      currentNode = nextNode;
   }
   
   firstNode = lastNode; // new first node
}

---

(b)

The complexity is Theta(size) because the while loop iterates size times and each iteration takes Theta(1) time.

(c)

The above code together with sample test program is in the file ChainWithReverse.java.