GATE drill: tracing pointer-manipulation code on linked lists

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• In a linked queue, which pointer must be reset when the last item is dequeued? from Lesson 3.4.4
• With slow/fast pointers, where does slow stop for a 7-node list? from Lesson 3.4.2
• What is FIFO? from Lesson 3.3.1

1 · The Hook

🎣

GATE likes to show a ten-line function full of p->next->next and ask what the list looks like afterwards. Reading such code in your head is error-prone. A disciplined method — draw the boxes, give every pointer a name, update one arrow per line — makes these questions routine.

2 · Predict First

🤔

What does this print?

struct node *moveLastToFront(struct node *head)
{
    struct node *p = head, *q = NULL;
    if (head == NULL || head->next == NULL) return head;
    while (p->next != NULL) {
        q = p;
        p = p->next;
    }
    q->next = NULL;
    p->next = head;
    head = p;
    return head;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6};
    printList(moveLastToFront(build(a, 6)));
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

6 1 2 3 4 5

p walks to the last node with q one step behind it. q becomes the new last node (q->next = NULL); p is linked in front of the old head and becomes the head.

The tracing method

• Draw the nodes as boxes with their values; draw every next arrow.
• Write each pointer variable’s name under the node it points to.
• Execute one statement at a time: an assignment to x->next redraws one arrow; an assignment to a pointer variable moves its label.
• Evaluate p->next->next from left to right using the current drawing.
• At the end, read the list from the head following arrows.

Pattern: change data vs change links

Some functions swap data (the links stay, values move); others rewire links (values stay with their nodes). Both give the same printed list but differ in which nodes the caller’s pointers now hold.

void swapPairs(struct node *p)
{
    int t;
    while (p != NULL && p->next != NULL) {
        t = p->data;
        p->data = p->next->data;
        p->next->data = t;
        p = p->next->next;
    }
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6, 7};
    struct node *h = build(a, 7);
    swapPairs(h);
    printList(h);
    return 0;
}

Output

2 1 4 3 6 5 7

Pattern: skipping nodes

p->next = p->next->next unlinks one node. Inside a loop that then moves p = p->next, every second node disappears:

void deleteAlternate(struct node *p)
{
    struct node *gone;
    while (p != NULL && p->next != NULL) {
        gone = p->next;
        p->next = gone->next;
        free(gone);
        p = p->next;
    }
}

int main(void)
{
    int a[] = {10, 20, 30, 40, 50};
    struct node *h = build(a, 5);
    deleteAlternate(h);
    printList(h);
    return 0;
}

Output

10 30 50

Pattern: recursion over a list

Recursion on p->next visits nodes forwards before the call and backwards after it (Lesson 2.1.2). Jumping by p->next->next visits every other node:

void f(struct node *p)
{
    if (p == NULL) return;
    printf("%d ", p->data);
    if (p->next != NULL)
        f(p->next->next);
    printf("%d ", p->data);
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6};
    f(build(a, 6));
    printf("\n");
    return 0;
}

Output

1 3 5 5 3 1

Pattern: recursive relinking

struct node *g(struct node *p)
{
    struct node *q;
    if (p == NULL || p->next == NULL) return p;
    q = p->next;
    p->next = g(q->next);
    q->next = p;
    return q;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5};
    printList(g(build(a, 5)));
    return 0;
}

Output

2 1 4 3 5

g swaps the first two nodes by links and recursively fixes the rest: q becomes the new front, p points to the processed remainder.

4 · Visual

Tracing moveLastToFront on 1 2 3 4 5 6:

start:     head
           [1]->[2]->[3]->[4]->[5]->[6]->NULL
            p
loop end:                           q    p
q->next = NULL:  [1]->[2]->[3]->[4]->[5]->NULL      [6]
p->next = head:  [6]->[1]->[2]->[3]->[4]->[5]->NULL
head = p:        head = [6]          -> prints 6 1 2 3 4 5

Labels move with assignments to pointer variables; arrows move with assignments to ->next.

Result of moveLastToFront: the old last node is now first.

5 · Worked Examples

Example 1 Easy

What does this print?

void deleteAlternate(struct node *p)
{
    struct node *gone;
    while (p != NULL && p->next != NULL) {
        gone = p->next;
        p->next = gone->next;
        free(gone);
        p = p->next;
    }
}

int main(void)
{
    int a[] = {10, 20, 30, 40, 50};
    struct node *h = build(a, 5);
    deleteAlternate(h);
    printList(h);
    return 0;
}

Solution

p = 10: unlink 20 → p = 30: unlink 40 → p = 50, whose next is NULL: stop.

Output

10 30 50

Example 2 Medium

What does this print?

void f(struct node *p)
{
    if (p == NULL) return;
    printf("%d ", p->data);
    if (p->next != NULL)
        f(p->next->next);
    printf("%d ", p->data);
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6};
    f(build(a, 6));
    printf("\n");
    return 0;
}

Solution

f(1) prints 1 and calls f(3); f(3) prints 3, calls f(5); f(5) prints 5; its next is 6, whose next is NULL: f(NULL) returns. Then the prints after the calls: 5, 3, 1.

Output

1 3 5 5 3 1

Example 3 GATE

What does this print?

int mystery(struct node *p)
{
    int s = 0, sign = 1;
    while (p != NULL) {
        s = s + sign * p->data;
        sign = -sign;
        p = p->next;
    }
    return s;
}

int main(void)
{
    int a[] = {9, 4, 7, 2, 6};
    struct node *h = build(a, 5);
    h->next->next = h->next->next->next;    /* unlink 7 */
    printf("%d\n", mystery(h));
    return 0;
}

Solution

h->next is the node 4. The left side h->next->next is that node’s next field; the right side h->next->next->next is the node 2. So node 4 now points to node 2 and 7 is skipped: 9 → 4 → 2 → 6. mystery alternates signs: 9 − 4 + 2 − 6 = 1.

Output

1

6 · GATE Traps

⚠️

• Evaluate p->next->next on the current drawing; it changes after every link assignment.
• q lagging one step behind p is the standard way to reach the second-to-last node.
• Swapping data and relinking nodes print the same list but are different operations.
• A loop that unlinks p->next and then moves p skips every second node.
• After relinking, the caller’s head may no longer be the first node; use the returned head.

8 · Memory Hook

🧠

“Draw the train, label the porters.” Every pointer variable is a porter standing at a coach; every ->next assignment re-couples one joint.

9 · Connect the Dots

Phase 3 is complete: arrays, stacks, queues and linked lists, each with array and linked versions. All of them are linear: every item has at most one successor. Phase 4 asks: how do we organise data where an item can have several successors, like a family tree or folders inside folders?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ2 marksOutput

What does this print?

void swapPairs(struct node *p)
{
    int t;
    while (p != NULL && p->next != NULL) {
        t = p->data;
        p->data = p->next->data;
        p->next->data = t;
        p = p->next->next;
    }
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6, 7};
    struct node *h = build(a, 7);
    swapPairs(h);
    printList(h);
    return 0;
}

• (A) 7 6 5 4 3 2 1
• (B) 2 1 4 3 6 5
• (C) 1 2 3 4 5 6 7
• (D) 2 1 4 3 6 5 7

Q2MCQ2 marksOutput

What does this print?

struct node *g(struct node *p)
{
    struct node *q;
    if (p == NULL || p->next == NULL) return p;
    q = p->next;
    p->next = g(q->next);
    q->next = p;
    return q;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5};
    printList(g(build(a, 5)));
    return 0;
}

• (A) 2 1 4 3 5
• (B) 2 1 3 4 5
• (C) 5 4 3 2 1
• (D) 1 2 3 4 5

Q3NAT2 marksOutput

What value does this print?

int mystery(struct node *p)
{
    int s = 0, sign = 1;
    while (p != NULL) {
        s = s + sign * p->data;
        sign = -sign;
        p = p->next;
    }
    return s;
}

int main(void)
{
    int a[] = {9, 4, 7, 2, 6};
    struct node *h = build(a, 5);
    h->next->next = h->next->next->next;    /* unlink 7 */
    printf("%d\n", mystery(h));
    return 0;
}

Numerical answer: ________

Q4MCQ1 markMethod

To reach the second-to-last node of a singly linked list in one pass, a common pattern is:

• (A) two pointers, q one step behind p
• (B) reverse the list first
• (C) binary search
• (D) start at the tail

Q5MSQ2 marksEffects

For a list 1 → 2 → 3 → 4 with head h, which statements leave the printed list as 1 → 3 → 4?

• (A) h->next = h->next->next;
• (B) h->next->data = 3; h->next->next = h->next->next->next;
• (C) h = h->next;
• (D) h->next->next = NULL;

11 · Rule Card

• Draw boxes + arrows; label pointer variables; one change per statement.
• p->next = p->next->next unlinks one node.
• q one step behind p reaches the second-to-last node.
• Data swap vs link swap: same printout, different nodes.
• Recursion over a list: before-call prints forwards, after-call backwards; p->next->next skips alternate nodes.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

pointer tracing methodunlinking with p->next = p->next->nexttrailing pointerdata swap vs link swap

13 · Answer Vault