Question

14.   p contains the elements 66, 9, 14, 52, 87, 14 and 17, in that order. Consider running the following line of code:

p = question4(p);

where question4 is the function defined below. Show the contents of p after the function call.

struct node* question4(struct node *list) {
struct node* a = list; struct node* b = list; struct node* c; if (a == NULL) return NULL; while ( a->next != NULL)
a = a ->next;
a->next = b; c = b->next; b->next = NULL;
return c;
}

Answer:

15.   Write a function that takes in a pointer to the front of a linked list and returns 1 if all the nodes in the linked list are in sorted order (from smallest to largest, with repeats allowed), and 0 otherwise. The prototype is given below:

int isSorted(struct node* list) {

16.   Write a function that takes in a pointer to the head of a linked list, a value to insert into the list, val, and a location in the list in which to insert it, place, which is guaranteed to be greater than 1, and does the insertion. If place number of items aren’t in the list, just insert the item in the back of the list. You are guaranteed that the linked list into which the inserted item is being added is not empty. The prototype is given below:

void insertToPlace(struct node* list, int val, int place) {


17.   Write a function that operates on a linked list of integers. Your function should insert a new node containing the value 2 after every node that contains the value 4. Make use of the list node struct and function header below.

void list_42(struct node* list) {

Answer 1

Question 14:

Given:

p contains elements 66, 9, 14, 52, 87, 14, and 17

Given snippet:

struct node* question4(struct node *list){ struct node* a = list; struct node* b = list; struct node* c; if(a == NULL) return NULL; while (a->next != NULL)             a = a ->next; a->next = b; c = b->next; b->next = NULL; return c; }

Content of p after the function call:

9, 14, 52, 87, 14, 17, 66

Explanation:

There are two pointers a and b. they are pointing to head. The loop will move the pointer (a) to the last node.

The pointer b is pointing to first node.

a-> next = b;

It is clear that a is pointing to b which makes the list circular.

c = b->next

the next of b is 9, hence the c will point to 9

b->next = NULL;

return c;

The first element will move to the end.

Here, 66 will be move to end and 9 will become the head node.

Therefore, the final content will be 9, 14, 52, 87, 14, 17, 66

Question 15:

Function that takes a pointer to the front of a linked list and returns 1 when all nodes in the linked list are in sorted order, otherwise returns 0.

Function:

// function prototype int isSorted (struct node* list) {      // temporary pointer      struct node* temp = list;      // iterate loop until the null value      while (temp->next != NULL) {                 // check if current value is greater than next value                 if (temp->value > temp->next->value)                      // return 0                      return 0;                 // point to next                 temp = temp->next;                 }                 // return 1                 return 1; }

Question 16:

Required function:

// function prototype void insertToPlace (struct node* list, int val, int place) {         // initialize current position         int currentPos = 1;         // dynamically allocate memory to new value         struct node* newVal = malloc(sizeof(struct node));         newVal->value = val;         newVal->next = NULL;         struct node* currentNode = list;         // iterate loop         while ((currentPos + 1)< place && currentNode->next != NULL) {                   currentNode = currentNode->next;                   currentPos++;          }          // check if next value of currentNode is null          if (currentNode->next == NULL)          {               // assign new value at the place of null                currentNode->next = newVal;           }           else if ((currentPost + 1) == place)           {                  newVal->next = currentNode->next;                  currentNode->next = newVal;            } }

Question 17:

Function that insert a new node containing the value 2 after every node that contains the value 4.

// function prototype void list_42 (struct node* list) {         struct node* newNode = NULL;         struct node* currentNode = list;         while (currentNode != NULL) {                  if (currentNode->data == 4)                  {                        newNode = malloc(sizeof(struct node));                        newNode->data = 2;                        newNode->next = currentNode->next;                        currentNode->next = newNode;                        currentNode = newNode->next;                     }                      else                             currentNode = currentNode->next;                     } }