Linked List

Consider a C Code fragment given below:

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will-

• append list m to the end of list n for all inputs

• either cause a null pointer dereference or append list m to the list n

• cause a null pointer dereference for all inputs

• append list n to the end of list m for all inputs

Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the list.What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

• O(n)

• O(log n)

• O(1)

• O(log²n)

What does the following function do for a given Linked List with first node as head?

• 
  Prints alternate nodes of Linked List

• Prints all nodes of linked list in reverse order

• Prints alternate nodes in reverse order

• Prints all nodes of linked lists

The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end of the function. 

What should be added in place of "/*ADD A STATEMENT HERE*/", so that the function correctly reverses a linked list.

• *head_ref = prev;

• *head_ref = current;

• *head_ref = next;

• 
  *head_ref = NULL;

What is the output of following function in which start is pointing to the first node of the following linked list 1->2->3->4->5->6 ?

• 1 4 6 6 4 1

• 1 3 5 1 3 5

• 1 2 3 5

• 
  1 3 5 5 3 1

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. Choose the correct alternative to replace the blank line. 

• q = NULL; p->next = head; head = p;

• q->next = NULL; head = p; p->next = head;

• head = p; p->next = q; q->next = NULL;

• q->next = NULL; p->next = head; head = p;

Consider the function f defined below:
For a given linked list p, the function f returns 1 if and only if

• not all elements in the list have the same data value.

• the elements in the list are sorted in non-decreasing order of data value

• the elements in the list are sorted in non-increasing order of data value

• None of them

What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.

• O(1) and O(n)

• O(1) and O(1)

• O(n) and O(1)

• O(n) and O(n)

Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

• Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b)Update the pointer of node X to the node after the next node. Delete next of X.

• Possible if size of linked list is even.

• Possible if size of linked list is odd

• Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X

Consider the following function to traverse a linked list. 

Which of the following is FALSE about above function?

• The function may crash when the linked list is empty

• The function doesn\'t print the last node when the linked list is not empty

• 
  The function is implemented incorrectly because it changes head

• None of the above