Question

Complete Chapter 20 Programming Challenge 3. Modivy the LinkedList1 class by adding sort() and reverse(). sort() sorts the list in alphabetical order. reverse() reverses the order of the list. Make sure that you use recursion to implement these methods. no points will be given for non-recursive mehtods. Extend the GUI LinkedList1Demo class to support sort and reverse commands and use it to test the new methods.

Note: Both the LinkedList1 and the GUI LinkedList1Demo are available in the Source Code provided.

Answer 1

Since you have not provided the code of LinkedList1.java and LinkedList1Demo.java, i am providing the sort() and reverse() methods based on my understand. Feel free to reach out in case of any enquiries.

Sort()

node sortedMerge(node a, node b)

    {

        node result = null;

        /* Base cases */

        if (a == null)

            return b;

        if (b == null)

            return a;

  

        /* Pick either a or b, and recur */

        if (a.val <= b.val) {

            result = a;

            result.next = sortedMerge(a.next, b);

        }

        else {

            result = b;

            result.next = sortedMerge(a, b.next);

        }

        return result;

    }

  

    node mergeSort(node h)

    {

        // Base case : if head is null

        if (h == null || h.next == null) {

            return h;

        }

  

        // get the middle of the list

        node middle = getMiddle(h);

        node nextofmiddle = middle.next;

  

        // set the next of middle node to null

        middle.next = null;

  

        // Apply mergeSort on left list

        node left = mergeSort(h);

  

        // Apply mergeSort on right list

        node right = mergeSort(nextofmiddle);

  

        // Merge the left and right lists

        node sortedlist = sortedMerge(left, right);

        return sortedlist;

    }

  

    // Utility function to get the middle of the linked list

    node getMiddle(node h)

    {

        // Base case

        if (h == null)

            return h;

        node fastptr = h.next;

        node slowptr = h;

  

        // Move fastptr by two and slow ptr by one

        // Finally slowptr will point to middle node

        while (fastptr != null) {

            fastptr = fastptr.next;

            if (fastptr != null) {

                slowptr = slowptr.next;

                fastptr = fastptr.next;

            }

        }

        return slowptr;

    }

Reverse()

node reverseUtil(node curr, node prev) {

  

        /* If last node mark it head*/

        if (curr.next == null) {

            head = curr;

  

            /* Update next to prev node */

            curr.next = prev;

              

            return head;

        }

  

        /* Save curr->next node for recursive call */

node next1 = curr.next;

  

        /* and update next ..*/

        curr.next = prev;

  

        reverseUtil(next1, curr);

        return head;

    }