Structure Modification and Pointer Logic MCQs: 10 Solved Linked List Questions

Most linked-list MCQs are decided by a single line, not by the whole algorithm: the predecessor whose next was never rewritten, the head the caller is still holding after the reversal, the final node whose next was never set at all. Each of the ten questions here is settled by writing the pointers down before and after the change, so a wrong option becomes visibly wrong rather than merely unlikely. If you want the whole data-structures sequence in order, the Coding & DSA Courses for Placements cover it.

1. Structure modification MCQs: the three checks to make before tracing

A pointer question usually fails in one of three places. You lose track of which pointer the caller is actually holding, you rewrite one link and miss the second one that had to change with it, or you change the right links and leave behind a node that nothing points to any more. One check covers each.

Do all three by hand before you read the answer line. A trace that names the access pointer, lists the changed links and then re-walks the chain leaves a plausible-looking wrong option nowhere to hide.

2. Linked-list reversal MCQs: whole list, missing head update and groups of k

Q1. Reverse a singly linked list in constant extra space

GATE 2022. See the solved question.

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

• (a) The best algorithm for the problem takes Theta(n) time in the worst case.

• (b) The best algorithm for the problem takes Theta(n log n) time in the worst case.

• (c) The best algorithm for the problem takes Theta(n^2) time in the worst case.

• (d) It is not possible to reverse a singly linked list in O(1) space.

Answer: (a).

Trace (prev,current) as (NULL,a), (a,b), (b,c), (c,d), (d,e), (e,NULL); then set head=e. One visit per node is Theta(n) time and three pointers are O(1) space. See Pointers in C for GATE.

Q2. Supply the missing final statement in iterative reversal

See the solved question.

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

struct node
{
        int data;
        struct node* next;
};

/* head_ref is a double pointer which points to head (or start) pointer of linked list */
static void reverse(struct node** head_ref)
{
        struct node* prev = NULL;
        struct node* current = *head_ref;
        struct node* next;
        while (current != NULL)
        {
                next = current->next;
                current->next = prev;
                prev = current;
                current = next;
        }
        /*ADD A STATEMENT HERE*/
}

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

• (a) *head_ref = prev;

• (b) head_ref = current;

• (c) head_ref = next;

• (d) *head_ref = NULL;

Answer: (a).

For a list 10→20→30, the loop leaves prev at 30→20→10→NULL and current=NULL; *head_ref=prev; updates the caller's head.

Q3. Reverse consecutive groups of size k

See the solved question.

What is the time complexity of the best-known algorithm for reversing a continuous sub-list of given size k in a singly linked list for example if the given linked list is 20 → 40 → 60 → 80 → 100 → 120 → 140 → 160 → NULL and k is 3 then the output should be 60 → 40 → 20 → 120 → 100 → 80 → 160 → 140 → NULL? (Where n is the number of nodes in the linked list and n>3.)

• (a) O(k.n)

• (b) O(n . log k)

• (c) O(n)

• (d) O(n^2)

Answer: (c).

With k = 3 the eight nodes split into groups of 3, 3 and 2, and the trailing group of 2 is reversed like any other, which is why the output ends 160 → 140. Every node is touched a constant number of times, eight visits in all, so the work is O(n) and not O(k.n).

3. Duplicate removal and deletion when only a node pointer is available

Q4. Count comparisons and retained distinct nodes

GATE 1997. See the solved question.

Consider the following C code fragment that removes duplicates from an ordered singly linked list of integers.

typedef struct Node {
    int val;
    struct Node *next;
} Node;

Node *remove_duplicates(Node *head, int *j) {
    Node *t1, *t2;
    *j = 0;
    t1 = head;
    if (t1 != NULL)
        t2 = t1->next;
    else
        return head;
    *j = 1;
    if (t2 == NULL)
        return head;
    while (t2 != NULL) {
        if (t1->val != t2->val) {    // S1
            // S2 starts
            (*j)++;
            t1->next = t2;
            t1 = t2;
            // S2 ends
        }
        t2 = t2->next;
    }
    t1->next = NULL;
    return head;
}

Assume the list contains n elements (n >= 2).

(i) How many times is the comparison in S1 made?

(ii) What are the minimum and maximum numbers of times the S2 block executes?

(iii) What does the value stored in *j represent when the function completes?

• (a) (i) n - 1 times; (ii) minimum 0 and maximum n - 1 times; (iii) *j stores the number of distinct nodes in the list.

• (b) (i) n times; (ii) minimum 0 and maximum n - 1 times; (iii) *j stores the number of distinct nodes in the list.

• (c) (i) n - 1 times; (ii) minimum 1 and maximum n - 1 times; (iii) *j stores the number of distinct nodes in the list.

• (d) None of the above

Answer: (a).

Take [1,1,2,2,2,5], so n = 6. t2 walks the five nodes after the head, so the S1 comparison runs n - 1 = 5 times. It is true twice, at the first 2 and at the 5, so S2 executes twice and *j finishes at 3, the number of distinct values. S2 runs 0 times when every element is equal and n - 1 times when all of them are distinct.

Q5. Delete a middle node without the head pointer

See the solved question.

In a singly linked list, if a node ptr points to the middle node, and you are given only a pointer to ptr (not to head), how can you delete that node?

• (a) It cannot be deleted without head pointer

• (b) Copy the data of the next node into ptr and delete the next node

• (c) Move ptr backward and delete it

• (d) Free ptr directly

Answer: (b).

At 30 in 10→20→30→40→NULL, copy 40 into ptr, bypass and free that successor, producing 10→20→40→NULL. A tail cannot be deleted this way.

4. Insertion and deletion operations: which link actually has to change

Q6. Linked-list deletion versus an array operation

CoCubes 2025. See the solved question.

Which of the following operations is performed more efficiently by Linked List than by Array?

• (a) Deletion

• (b) Accessing the element at a specific index

• (c) Iteration

• (d) Sorting

Answer: (a).

Given the node or predecessor, deletion changes constant links; an array may shift elements. List search remains O(n).

Q7. Insert a newly allocated node at the beginning

ISRO 2013. See the solved question.

The following steps in a linked list

p = getnode()

info (p) = 10

next (p) = list

list = p

result in which type of operation?

• (a) pop operation in stack

• (b) removal of a node

• (c) inserting a node at beginning

• (d) modifying an existing node

Answer: (c).

Starting from a list whose first node is 20, next(p)=list links new node 10 before 20; list=p makes it the first node.

Q8. Delete the first data node after a sentinel head

LTI Mindtree 2025. See the solved question.

What is the functionality of the following piece of code?

public Object delete_key()
{
if(count == 0)
{
System.out.println("Q is empty");
System.exit(0);
}
else
{
Node cur = head.getNext();
Node dup = cur.getNext();
Object e = cur.getEle();
head.setNext(dup);
count--;
return e;
}
}

• (a) Delete the second element in the list

• (b) Return but not delete the second element in the list

• (c) Delete the first element in the list

• (d) Return but not delete the first element in the list

Answer: (c).

In sentinel chain head→A→B→C, cur=A, dup=B, and head.setNext(B) bypasses A; its element is returned.

5. Sentinel emptiness and uninitialised next pointers

Q9. Interpret S->Next == NULL in a linked-list stack

NVS 2022. See the solved question.

Consider a stack S implemented using a linked list.

When does the following function return TRUE?

int f1(stack S)
{
    return S->Next == NULL;
}

A) When the stack is full.

B) When the stack is empty.

C) When no memory is available.

Mark the correct option.

• (a) Only (A) is correct

• (b) Only (B) is correct

• (c) Only (C) is correct

• (d) Only (B) and (C) are correct

Answer: (b).

For sentinel S, S->Next is the first data node, so NULL means empty.

Q10. Trace an uninitialised final next pointer

LTI Mindtree 2025. See the solved question.

Consider the following ANSI C program:

#include<stdio.h>
#include<stdlib.h>
struct Node {
  int value;
  struct Node *next;
};
int main() {
  struct Node *boxE, *head, *boxN;
  int index = 0;
  boxE = head = (struct Node *) malloc(sizeof(struct Node));
  head->value = index;
  for (index = 1; index <= 3; index++) {
    boxN = (struct Node *) malloc(sizeof(struct Node));
    boxE->next = boxN;
    boxN->value = index;
    boxE = boxN;
  }
  for (index = 0; index <= 3; index++) {
    printf("Value at index %d is %d\n", index, head->value);
    head = head->next;
    printf("Value at index %d is %d\n", index + 1, head->value);
  }
}

Which one of the following statements is correct about the program?

• (a) Upon execution, the program creates a linked-list of five nodes

• (b) Upon execution, the program goes into an infinite loop

• (c) It has a missing return which will be reported as an error by the compiler

• (d) It dereferences an uninitialized pointer that may result in a run-time error

Answer: (d).

Four nodes contain 0,1,2,3, but node 3's next is uninitialised. At index=3, dereferencing that indeterminate link is undefined behaviour and may cause a run-time error.

6. Structure modification and pointer logic: the short version and next practice step

Save next before you overwrite current->next, or the rest of the list is gone (Q1, Q2). Write the new head back through the double pointer, because the caller is still holding the old one (Q2). With only a node pointer in hand you delete by copying the successor's data forward and unlinking the successor, which is exactly why a tail node cannot be deleted that way (Q5).

Deletion is cheap only once you already hold the node or its predecessor; reaching it is still O(n), and that is what separates it from an array shift (Q6). A sentinel head is not a data node, so an empty list reads as head->next == NULL, not head == NULL (Q8, Q9). And a newly allocated final node needs its next set to NULL explicitly, or the last step of a traversal dereferences an indeterminate pointer (Q10).

Next, take the same tracing habit to Stacks and Queues MCQs and Binary Tree MCQs.

For the full data-structures sequence in order, use GATE Guidance by Sanchit Sir.