two Exercises from Astrachan: pages 565, 566: 12.13, 12.14
Reprinted here for those who do not have the book from last quarter.

12:13 Write a function Reverse( ) that reverses the order of the nodes in a linked list. Reverse the list by changing pointers, not by swapping info fields.

void Reverse(Node * & list)
// precondition:        list = (a b c . . . d)
// poscondition:        list = (d . . . c b a), list reversed

12:14 Write a function that doubles a linked list by duplicating each node, i.e. the list (a b c d) is changed into (a a b b c c d d). Use the header below where list is NOT passed by reference.

void DoubleList(Node * list)
// precondition:  if   list = (a b c d)
// postcondition: then list = (a a b b c c d d)

and two from the com1101 final plus one more:
Problem 3 (Pointers) Assume the following declarations:

struct Node {
    char data;
    Node* next;
};

Node* list;

And that the following linked list has been created:

For each of the following code segments, draw a NEAT picture showing the resuting lists.

a) Show the list and pointers: list, list1, list2, rear1, rear2 after the code is executed:

Node* list1 = NULL;
Node* list2 = NULL;
Node* rear1 = NULL;
Node* rear2 = NULL;

list1 = list;
rear1 = list1;
if (list != NULL){
	   list2 = list->next;
	   rear2 = list2;
}
else list2 = NULL;

while (rear1 != NULL) {
	   if (rear2 != NULL) {
		      rear1->next = rear2->next;
		      rear1 = rear2->next;
	   }
	   else {
		      rear1->next = NULL;
		      rear1 = NULL;
	   }
	
	   if (rear1 != NULL) {
		      rear2->next = rear1->next;
		      rear2 = rear1->next;
	   }
	   else {
		      rear2->next = NULL;
		      rear2 = NULL;
	   }
}

list1 = NULL;
list2 = NULL;
rear1 = NULL;
rear2 = NULL;

list1 = list;
rear1 = list;
while (rear1 != NULL) {
	   if (rear1->data == 'E') 
		      break;
	   else 
		      rear1 = rear1->next;
}
list2 = rear1->next;
rear2 = list2;
if (rear2 != NULL)
	   while (rear2->next != NULL)
		     rear2 = rear2->next;

list1 = NULL;
list2 = NULL;

ptr = list;
rear1 = list;

while (list != NULL){
	  ptr = list->next;
	  if (list->data == 'E'){
		     list->next = list1;
		     list1 = list;
	  }
	  else {
		    list->next = list2;
		    list2 = list;
	  }
	  list = ptr;
	  if (ptr != NULL) ptr=ptr->next;
}

Last Updated: June 1, 1997 11:30 am by