In the worst case, the number of comparisons needed to search singly linked list of length n for given elements is

Q. 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 form the list?

Q. An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Q. You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences.
The lower bound on the number of comparisons needed to solve this variant of sorting problem is

Q. Consider the following statements given below:

$S_1$: Consider a unweighted undirected connected graph G[V, E] worst case time complexity to check it two particular vertices U, V present in the graph is O (V + E). Check it two particular vertices U, V present in the graph is O (V + E).

$S_2$: Dijkstra's algorithm may produce incorrect result if it contain negative weight cycle.

$S_3$: The worst case running time complexity to search for an element in a balanced binary search tree with n element is O(n).

Which of the above statement is correct?

Q. The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order.

What will be the contents of the list after the function completes execution?

struct node
{
int value;
struct node *next;
};
void rearrange (struct node *list)
{
struct node *p, *q;
int temp;
if (!list $\mid$ $\mid$ !list $\to$ next)
return;
p = list;
q = list $\to$ next;
while (q)
{
temp = p $\to$ value;
p $\to$ value = q $\to$ value;
q $\to$ value = temp;
p = q$\to$ next;
q = p ? p $\to$ next : 0;
}
}