Linked List Practice Questions

The function performs pairwise swaps of the values in the linked list by iterating through nodes with pointers $p$ and $q$.

1. Initially, $p$ points to the node with value $1$ and $q$ points to $2$. They are swapped, resulting in $2, 1, \dots$. Then, $p$ moves to $3$ and $q$ to $4$.
2. In the next iteration, $3$ and $4$ are swapped, resulting in $2, 1, 4, 3, \dots$. Then, $p$ moves to $5$ and $q$ to $6$.
3. Finally, $5$ and $6$ are swapped, resulting in $2, 1, 4, 3, 6, 5, 7$. Since the next pointer of the node containing $7$ is null, $q$ becomes null, terminating the loop.
   The list contents become $2, 1, 4, 3, 6, 5, 7$.

We have $k = \lceil \log n \rceil$ sorted lists, each of size $m = \lfloor n / \log n \rfloor$. Using a min-heap of size $k$ to merge these lists, we perform $n$ total extract-min operations, where each operation takes $O(\log k)$ time. The total time complexity for merging all elements is $O(n \log k)$. Substituting $k = \lceil \log n \rceil$ into the expression, we obtain $O(n \log(\log n))$, which simplifies to $O(n \log \log n)$.

In a circular linked list representing a queue, if pointer $p$ points to the rear node, the front node is instantly accessible via $p \to next$. For enQueue, we insert a new node after $p$ and update $p$ to this new node in $O(1)$ time. For deQueue, we remove the node at $p \to next$ and update the links in $O(1)$ time. If $p$ pointed to the front, finding the rear would require an $O(n)$ traversal, making enQueue inefficient. Thus, pointing $p$ to the rear node enables $O(1)$ time complexity for both operations.

Cardinality involves a single pass through the list, taking $O(n)$ time. Membership testing requires traversing the list until the element is found, also taking $O(n)$ time. Conversely, intersection requires iterating through the first list of size $n$ and performing a membership check on the second list of size $m$, yielding $O(n \times m)$ time. Similarly, union involves inserting elements from one list into another while ensuring no duplicates, which also requires $O(n \times m)$ operations. Since $O(n \times m)$ is asymptotically slower than $O(n)$, union and intersection are the slowest operations.

To delete a node $x$ given its pointer $Q$ in a singly linked list, the standard technique is to copy the data from the node $Q \to next$ into $Q$ and then bypass $Q \to next$ by updating $Q \to next = Q \to next \to next$. This approach is $O(1)$. However, this method fails if $x$ is the last node, as $Q \to next$ would be $NULL$. In this case, one must traverse the entire list from the head to identify the predecessor of $x$ to set its next pointer to $NULL$. Since this traversal takes linear time, the worst-case complexity is $O(n)$.

The function $f(p)$ uses recursion to evaluate the list:

1. If $p == NULL$ (empty list) or $p \to next == NULL$ (single element), it returns 1.
2. Otherwise, it checks if the current node's data is less than or equal to the next node's data: $p \to data \le p \to next \to data$.
3. The result of this condition is combined with the recursive call $f(p \to next)$, ensuring the comparison holds for all adjacent pairs.
4. By induction, this evaluates if $data_i \le data_{i+1}$ for every node in the linked list.
5. Consequently, the function returns 1 if and only if the list is sorted in non-decreasing order.

A linked list is a linear data structure where elements are stored in nodes, and access is restricted to sequential traversal starting from the head node. Searching for a specific element requires comparing it against each node's data one by one. In the worst-case scenario, the target element is either at the final position or completely absent from the list. Consequently, the search algorithm must visit every node, resulting in exactly $n$ comparisons for a list of length $n$.

To concatenate two circular doubly linked lists in $O(1)$ time, we perform constant-time pointer re-linking at the boundaries. Let $H_1, T_1$ represent the head and tail of the first list, and $H_2, T_2$ represent the second. Because the structure allows direct access to the tail via $head \to prev$, we can link $T_1$ to $H_2$ and $T_2$ to $H_1$ using operations such as $T_1 \to next = H_2$, $H_2 \to prev = T_1$, $T_2 \to next = H_1$, and $H_1 \to prev = T_2$. This requires only a fixed number of pointer updates, unlike arrays which require $O(n)$ time for copying or singly linked lists which require $O(n)$ time for traversal. Therefore, the circular doubly linked list allows for $O(1)$ concatenation.

1. Statement I is true: In a hash table, as the number of entries $n$ increases relative to the slot size $m$, the load factor $\alpha = \frac{n}{m}$ rises, increasing collision probability.
2. Statement II is false: Recursion often incurs significant memory overhead due to stack frames, making it generally less efficient than iterative alternatives.
3. Statement III is true: The worst-case time complexity of Quicksort is $O(n^2)$, occurring when partitions are consistently unbalanced.
4. Statement IV is false: Binary search requires $O(1)$ random access to operate in $O(\log n)$; accessing the middle of a linear linked list requires $O(n)$ time, rendering it inefficient.
5. Since I and III are true, option D is the correct choice.

To merge two sorted lists of sizes $m$ and $n$, we maintain two pointers, one for each list, and compare the elements they reference. In each step, we move the smaller element to the merged list and advance its corresponding pointer. The worst-case scenario occurs when we compare nearly every element from both lists until one list is exhausted, resulting in a maximum of $(m+n-1)$ comparisons. Since the number of operations grows linearly with the total number of elements, the time complexity is $O(m+n)$.

Linked lists are suitable for: Insertion sort : No need to swap here just find appropriate place and join the link Polynomial manipulation : Linked List is a natural solution for polynomial manipulation Radix sort : Here we are putting digits according to same position(unit,tens) into buckets; which can be effectively handled by linked lists. Not Suitable for: Binary search : Because finding mid element itself takes $O(n)$ time. So, Option B is answer.

In a circular singly linked list, inserting a new node $N$ between an existing node $P$ and its successor requires exactly two pointer modifications. First, the $next$ pointer of the new node $N$ is updated to point to the current successor of $P$, represented as $N \to next = P \to next$. Second, the $next$ pointer of node $P$ is updated to reference the new node $N$, represented as $P \to next = N$. These two operations successfully integrate the new node while preserving the circular structure.