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

(a)

We can use essentially the same code as used in Exercise 15 to merge two chains. We must change all occurrences of ExtendedChain to HeadCircularList. The modified code is given below.

---

public class MergeHeadCircularList
{
   /** merge the sorted lists a and b */
   public static HeadCircularList merge(HeadCircularList a, HeadCircularList b)
   {
      // initialize iterators for a and b
      Iterator ia = a.iterator();     // iterator for a
      Iterator ib = b.iterator();     // iterator for b
      Comparable elementA = null;     // current element of a
      if (ia.hasNext())
         elementA = (Comparable) ia.next();
      Object elementB = null;         // current element of b
      if (ib.hasNext())
         elementB = ib.next();
   
      // create result list
      HeadCircularList c = new HeadCircularList();
   
      // do the merge
      while (elementA != null && elementB != null)
      {
         if (elementA.compareTo(elementB) <= 0)
         {// elementA goes next
            c.add(elementA);
            if (ia.hasNext())
               elementA = (Comparable) ia.next();
            else
               elementA = null;
         }
         else
         {// elementB goes next
            c.add(elementB);
            if (ib.hasNext())
               elementB = ib.next();
            else
               elementB = null;
         }
      }
   
      // add remaining elements
      if (elementA != null)
         c.add(elementA);
      if (elementB != null)
         c.add(elementB);

      // at most one of a and b can be nonempty now
      while (ia.hasNext())
         c.add(ia.next());
   
      while (ib.hasNext())
         c.add(ib.next());
   
      return c;
   }
}

(b)

In each iteration of the first while loop, we move one node right either in a or either in b. So, the complexity of this loop is O(a.size + b.size). The complexity of the second while loop is O(a.size), and that of the third loop is O(b.size). So, the overall complexity is O(a.size + b.size).

(c)

The test program and output are in the files MergeHeadCircularList.*.

(d)

The code for the member method is given below.

---

public class HeadCircularListWithMerge extends HeadCircularList
{
   /** make this the result of merging the sorted lists a and b 
     * following the merge, both a and b are empty */
   public void merge(HeadCircularListWithMerge a, HeadCircularListWithMerge b)
   {
      ChainNode ca = a.headerNode.next,     // pointer to current node in a
                cb = b.headerNode.next;     // pointer to current node in b

      ChainNode ct = headerNode;            // pointer to last node in this

      // merge from a and b until one becomes empty
      while (ca != a.headerNode && cb != b.headerNode)
         if (((Comparable) ca.element).compareTo(cb.element) <= 0)
         {// a element goes first
            ct.next = ca;
            ct = ca;
            ca = ca.next;
         }
         else
         {// b element is smaller
            ct.next = cb;
            ct = cb;
            cb = cb.next;
         }

      // append the rest
      if (ca != a.headerNode)
      {
         ct.next = ca;
         ct = a.lastNode;
      }  

      if (cb != b.headerNode)
      {
         ct.next = cb;
         ct = b.lastNode;
      }

      // make into a circular list
      ct.next = headerNode;
      lastNode = ct;
      size = a.size + b.size;

      // make a and b empty
      a.clear();
      b.clear();

      return;
   }
}

(e)

In each iteration of the while loop, we move one node right either in a or in b. So, the complexity of this loop is O(a.size + b.size). The remainder of the code takes Theta(1) time. So, the overall complexity is O(a.size + b.size).

(f)

The test program and output are in the files HeadCircularListWithMerge.*.