Question 1. Implement a linked list reverse function [6]

Suppose we have the following definition for a list node and prototype for a function:

struct Node { int data; Node *next, *prev; };

bool Reverse(Node* &front, Node* &back);

The two parameters are supposed to be pointers to the two ends of a linked list, and the purpose of the function is to reverse the order of the data in the linked list. I.e. if the data values in the list started out as 1, 13, 27, 8 (going front to back) then after the function finishes the order of the values in the list should be 8, 27, 13, 1. The function should return true if successful, false if anything goes wrong.

Provide an appropriate implementation of the function. (You can choose between reorganizing the nodes themselves or simply moving the data values within the nodes.)

SAMPLE SOLUTION 1 walk towards middle from ends bool Reverse(Node* &front, Node* &back) { // use two nodes to walk from the ends towards // the middle, swapping values as they go // stop and return true if they meet, // return false otherwise // start at the ends of the list Node *forward = front; Node *backward = back; while ((forward != NULL) && (backward != NULL)) { // if the two pointers are the same then they have met // in the middle of an odd length list, so return true if (forward == backward) return true; // check for a broken list: front != back // but one of the pointers is null if ((front == NULL) || (back == NULL)) return false; // otherwise swap their values int temp = forward->data; forward->data = backward->data; backward->data = temp; // if forward and backward are adjacent then they have met // in the middle of an even length list, so return true if (forward->next == backward) return true; // otherwise move both of them one spot closer to the middle forward = forward->next; backward = backward->prev; } // if we get out of the loop then one or both pointers // reached an endpoint without ever meeting each other return false; } SAMPLE SOLUTION 2: just reverse all the pointers bool Reverse(Node* &front, Node* &back) { Node *swapnode; Node *current = front; while (current != NULL) { // swap the next/prev pointers for the node // we're currently working on swapnode = current->next; current->next = temp->prev; current->prev = swapnode; // move to the next node in line current = swapnode; } // swap the front and back pointers swapnode = front; front = back; back = swapnode; return true; }

SAMPLE SOLUTION 3: recursive bool Reverse(Node* &front, Node* &back) { // base case if (front == back) return true; // check for a broken list: front != back // but one of the pointers is null if ((front == NULL) || (back == NULL)) return false; // pull off front item Node *oldfront = front; front = front->next; front->prev = NULL; // call recursively if (!Reverse(front, back)) return false; // put old front item on the back back->next = oldfront; oldfront->prev = back; oldfront->next = NULL; back = oldfront; return true; } SAMPLE SOLUTION 4: using a second list bool Reverse(Node* &front, Node* &back) { // set up a second list Node *newFront = NULL; Node *newBack = NULL; // remove items one at a time from front of original, // inserting them at the front of the second list while (front != NULL) { // check for a broken list: // front->next is null but front != back if ((front != back) && (front->next == NULL) return false; // remove the next element from the front of the original list Node *n = front; front = front->next; if (front) front->prev = NULL; else back = NULL; // attach it to the front of the new list n->prev = NULL; n->next = newFront; if (newFront) newFront->prev = n; else newBack = n; newFront = n; } // set front and back to point to new list front = newFront; back = newBack; return true; }