Self-checkedTier 1 20 min readpds.linked-list-operations

Linked list operations

The standard things GATE does with singly linked lists: delete by value (head, middle, last), delete a node you only hold a pointer to, reverse (iteratively and recursively), find the middle and the k-th from the end with two pointers, detect and locate a cycle, and merge two sorted lists. Each is traced pointer by pointer and run for real.

Why it exists

Building and walking a list is easy. The exam questions are about rewiring: remove a node without losing the rest, turn the list around without allocating anything, find the middle without knowing the length, discover that a list is secretly a loop. Each is a short pointer dance, and each goes wrong in the same few ways. This page works them through one pointer assignment at a time.

All examples use the node from the previous page:

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

Prerequisites

Singly linked lists

Precise definitions

Predecessor. The node whose next points at a given node. A singly linked list cannot find it without walking from the head.
Unlinking a node means changing its predecessor's next so that the node is no longer on the chain. Freeing it releases its memory. The rule is: never read a node after freeing it. Save what you need from it (usually next) and unlink it, then free it.
Sentinel (dummy) node. An extra node placed before the first real node. Because every real node then has a predecessor, the code for "first node" and "other node" becomes the same.
Pointer to a pointer. struct node **pp = &head; points at the variable that holds the address of a node (first head, later the next member of some node). Writing *pp = ... changes whichever link currently leads to the node of interest, with no special case for the head.
Two-pointer technique. Two pointers walk the same list at different speeds or with a fixed gap. This finds the middle, the $k$ -th from the end and cycles in one pass without counting.
Cycle. A list whose chain of next pointers never reaches NULL because some node points back to an earlier node (or to itself).

Costs at a glance

Operation	Time	Extra space
Delete by value	$O(n)$ (find it), $O(1)$ to unlink	$O(1)$
Delete a node given only a pointer to it (not the last)	$O(1)$	$O(1)$
Reverse (iterative)	$O(n)$	$O(1)$
Reverse (recursive)	$O(n)$	$O(n)$ call stack
Middle, $k$ -th from end, cycle detection (two pointers)	$O(n)$ , one pass	$O(1)$
Merge two sorted lists of lengths $m$ and $n$	$O(m + n)$	$O(1)$ (relinking nodes)

How it works

Deleting a node

To delete the node cur, the previous node must be made to skip it. That is why the walk keeps prev one step behind cur. Step through the run. Two things to notice. First, after prev->next = cur->next, node 20 is already off the chain, but it is still allocated and cur still points at it, so nothing is leaked (it would be, if cur were overwritten without freeing it). Second, deleting the first node has no prev: head itself moves, and the old first node must be remembered in a temporary so that it can be freed.

Deleting nodes from a singly linked list

Real run, real addresses

C source

1#include <stdio.h>

2#include <stdlib.h>

4struct node {

5 int data;

6 struct node *next;

7};

9int main(void) {

10 struct node *head = NULL, *n;

11 int vals[3] = {30, 20, 10};

12 for (int i = 0; i < 3; i++) {

13 n = malloc(sizeof *n);

14 n->data = vals[i];

15 n->next = head;

16 head = n;

17 }

18 struct node *prev = NULL, *cur = head;

19 while (cur != NULL && cur->data != 20) {

20 prev = cur;

21 cur = cur->next;

22 }

23 prev->next = cur->next;

24 free(cur);

25 cur = NULL;

26 n = head;

27 head = head->next;

28 free(n);

29 n = NULL;

30 return 0;

31}

Stack

headpointer

node 10…d5f0

npointer

node 10…d5e8

Heap

node 30struct node

30…a2a0

data

↑node 20.next

NULL…a2a8

node 20struct node

20…a2c0

data

↑node 10.next

node 30…a2c8

node 10struct node

10…a2e0

data

↑head↑n

node 20…a2e8

Amber = changed in this step. Hover a cell for its full address. Arrows show where a pointer points; the small tag under a cell names the pointers aimed at it.

Step 1

The list is 10, 20, 30 (we inserted 30, 20, 10 at the front).

1 / 7

To delete a node you must change the next of the node before it, so a walk keeps a prev pointer one step behind cur. Produced by: real execution: every address and value is read from memory by the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog (ASLR off so the numbers are stable)

Reversing in place

Three pointers do the job. next saves the rest of the list, cur->next = prev turns the node round, then prev and cur both step forward. Without the saved next, the rest of the list would be lost the moment cur->next is overwritten. The run shows every node stays reachable the whole time.

Reversing a singly linked list in place

Real run, real addresses

C source

1#include <stdio.h>

2#include <stdlib.h>

4struct node {

5 int data;

6 struct node *next;

7};

9int main(void) {

10 struct node *head = NULL, *n;

11 int vals[3] = {30, 20, 10};

12 for (int i = 0; i < 3; i++) {

13 n = malloc(sizeof *n);

14 n->data = vals[i];

15 n->next = head;

16 head = n;

17 }

18 struct node *prev = NULL, *cur = head, *next = NULL;

19 while (cur != NULL) {

20 next = cur->next;

21 cur->next = prev;

22 prev = cur;

23 cur = next;

24 }

25 head = prev;

26 return 0;

27}

Stack

headpointer

node 10…d5e8

prevpointer

NULL…d5d0

curpointer

node 10…d5c8

nextpointer

NULL…d5c0

Heap

node 30struct node

30…a2a0

data

↑node 20.next

NULL…a2a8

node 20struct node

20…a2c0

data

↑node 10.next

node 30…a2c8

node 10struct node

10…a2e0

data

↑head↑cur

node 20…a2e8

Amber = changed in this step. Hover a cell for its full address. Arrows show where a pointer points; the small tag under a cell names the pointers aimed at it.

Step 1

The list is 10, 20, 30. We will reverse it with three pointers: prev (the already reversed part), cur (the node being fixed) and next (the rest of the list).

1 / 11

Three pointers walk the list. Each node's next is turned around once, and nothing is allocated or copied. Produced by: real execution: every address and value is read from memory by the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog (ASLR off so the numbers are stable)

Worked examples

EX 1Delete by value with a pointer to a pointer

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *range(int n) {
    struct node *head = NULL;
    for (int v = n; v >= 1; v--) {
        struct node *x = malloc(sizeof *x);
        if (x == NULL) exit(1);
        x->data = v;
        x->next = head;
        head = x;
    }
    return head;
}
 
static int del(struct node **head, int key) {
    struct node **pp = head;
    while (*pp != NULL && (*pp)->data != key) pp = &(*pp)->next;
    if (*pp == NULL) return 0;
    struct node *t = *pp;
    *pp = t->next;
    free(t);
    return 1;
}
 
static void show(const struct node *p) {
    for (; p != NULL; p = p->next) printf("%d ", p->data);
    printf("\n");
}
 
int main(void) {
    struct node *head = range(5);
    show(head);
    del(&head, 1);
    show(head);
    del(&head, 3);
    show(head);
    del(&head, 5);
    show(head);
    printf("%d\n", del(&head, 9));
    return 0;
}

Output:

Reading it. pp starts at &head, the variable that holds the first node's address. The loop advances pp to &(*pp)->next, the next member of the current node, until *pp is the node to remove. Then *pp = t->next redirects whichever link led to it: head when the node is first, an earlier node's next otherwise. The same three lines handle the first, a middle and the last node. Deleting 9 finds nothing and returns 0. (This program does not free the remaining nodes.)

EX 2Delete a node when you only have a pointer to it

GATE level

#include <stdio.h>
 
struct node {
    int data;
    struct node *next;
};
 
int main(void) {
    struct node n4 = {40, NULL}, n3 = {30, &n4}, n2 = {20, &n3}, n1 = {10, &n2};
    struct node *p = &n2;
    struct node *gone = p->next;
    p->data = gone->data;
    p->next = gone->next;
    for (struct node *q = &n1; q != NULL; q = q->next) printf("%d ", q->data);
    printf("\n%d\n", gone == &n3);
    return 0;
}

Output:

10 30 40
1

Reading it. To delete the node p points at (data 20) without the previous node, copy the next node's data into it and unlink the next node instead. The list reads 10, 30, 40, but physically the node that disappeared is the one that held 30 (gone), and the node that was n2 now holds 30.

Limits, which are favourite exam traps.

It does not work for the last node: there is no next node to copy from.
It changes which node holds which value, so any other pointer that pointed at *gone now dangles, and a pointer to n2 now "sees" a different value.
It works in $O(1)$ time, which is why it is asked.

EX 3Reverse a list, iteratively and recursively

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *range(int n) {
    struct node *head = NULL;
    for (int v = n; v >= 1; v--) {
        struct node *x = malloc(sizeof *x);
        if (x == NULL) exit(1);
        x->data = v;
        x->next = head;
        head = x;
    }
    return head;
}
 
static struct node *rev_iter(struct node *h) {
    struct node *prev = NULL;
    while (h != NULL) {
        struct node *next = h->next;
        h->next = prev;
        prev = h;
        h = next;
    }
    return prev;
}
 
static struct node *rev_rec(struct node *h) {
    if (h == NULL || h->next == NULL) return h;
    struct node *r = rev_rec(h->next);
    h->next->next = h;
    h->next = NULL;
    return r;
}
 
static void show(const struct node *p) {
    for (; p != NULL; p = p->next) printf("%d ", p->data);
    printf("\n");
}
 
int main(void) {
    struct node *head = range(5);
    head = rev_iter(head);
    show(head);
    head = rev_rec(head);
    show(head);
    return 0;
}

Output:

5 4 3 2 1
1 2 3 4 5

Iterative. The loop is exactly the animation: save next, point h backwards, step prev and h forward. $O(n)$ time, $O(1)$ extra space.

Recursive. rev_rec(h) first reverses the rest, so the list after h is already reversed and h->next is now the last node of the reversed part. Writing h->next->next = h appends h after it, and h->next = NULL makes h the new last node. The return value r is the new head, passed up unchanged. The recursion is $n$ deep, so it uses $O(n)$ stack (see recursion patterns).

EX 4The middle node with a slow and a fast pointer

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *range(int n) {
    struct node *head = NULL;
    for (int v = n; v >= 1; v--) {
        struct node *x = malloc(sizeof *x);
        if (x == NULL) exit(1);
        x->data = v;
        x->next = head;
        head = x;
    }
    return head;
}
 
static struct node *middle(struct node *h) {
    struct node *slow = h, *fast = h;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
 
int main(void) {
    printf("%d %d\n", middle(range(5))->data, middle(range(6))->data);
    return 0;
}

Output:

3 4

Reading it. fast moves two nodes for each one node of slow, so when fast reaches the end, slow is halfway. With 5 nodes the middle is the 3rd (data 3). With 6 nodes there are two middle nodes (3 and 4); this loop returns the second (data 4). If a question wants the first, use the loop condition fast->next != NULL && fast->next->next != NULL (after handling an empty list), which stops one step earlier. The condition fast != NULL && fast->next != NULL is the standard guard: the order of the two tests matters, because fast->next is only safe after fast != NULL.

EX 5Detect a cycle and find where it starts

GATE level

#include <stdio.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *cycle_start(struct node *h) {
    struct node *s = h, *f = h;
    while (f != NULL && f->next != NULL) {
        s = s->next;
        f = f->next->next;
        if (s == f) {
            s = h;
            while (s != f) {
                s = s->next;
                f = f->next;
            }
            return s;
        }
    }
    return NULL;
}
 
int main(void) {
    struct node a[5];
    for (int i = 0; i < 5; i++) {
        a[i].data = i + 1;
        a[i].next = i < 4 ? &a[i + 1] : &a[2];
    }
    struct node *st = cycle_start(&a[0]);
    int len = 1;
    for (struct node *p = st->next; p != st; p = p->next) len++;
    a[4].next = NULL;
    printf("%d %d %d\n", st->data, len, cycle_start(&a[0]) == NULL);
    return 0;
}

Output:

3 3 1

Reading it. The list is 1, 2, 3, 4, 5 and the last node points back to node 3, so nodes 3, 4, 5 form a cycle (length 3) entered at node 3.

Detection (Floyd's tortoise and hare). f moves 2, s moves 1. Inside a cycle the gap between them shrinks by 1 on every step, so they must meet: if there is a cycle, s == f happens within the cycle; if the list ends, f hits NULL first.

Finding the start. (Take $k \ge 1$ as the number of extra laps the fast pointer has made, take $d$ modulo $c$ , and note that $a$ may be larger than $c$ ; the argument still holds because $a + d$ is a multiple of $c$ .) When they meet, put one pointer back at the head and move both one step at a time: they meet again exactly at the first node of the cycle. (Reason: if the part before the cycle has length $a$ , the cycle length is $c$ and the meeting point is $d$ steps into the cycle, then $2(a + d) = a + d + kc$ , so $a = kc - d$ : walking $a$ steps from the head, and $a$ steps from the meeting point, lands both at the entry.) The run then cuts the cycle (a[4].next = NULL) and the function finds none: cycle_start returns NULL, so the comparison prints 1.

EX 6The k-th node from the end, in one pass

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *range(int n) {
    struct node *head = NULL;
    for (int v = n; v >= 1; v--) {
        struct node *x = malloc(sizeof *x);
        if (x == NULL) exit(1);
        x->data = v;
        x->next = head;
        head = x;
    }
    return head;
}
 
static struct node *kth_from_end(struct node *h, int k) {
    struct node *lead = h, *lag = h;
    for (int i = 0; i < k; i++) {
        if (lead == NULL) return NULL;
        lead = lead->next;
    }
    while (lead != NULL) {
        lead = lead->next;
        lag = lag->next;
    }
    return lag;
}
 
int main(void) {
    struct node *h = range(7);
    printf("%d %d\n", kth_from_end(h, 3)->data, kth_from_end(h, 7)->data);
    return 0;
}

Output:

5 1

Reading it. lead is first moved $k$ nodes ahead, creating a gap of $k$ . Then both move together until lead falls off the end. At that moment lag is $k$ nodes from the end: for the list 1 to 7 and $k = 3$ , that is the node holding 5; for $k = 7$ it is the first node. If the list is shorter than $k$ , the first loop reaches NULL and the function returns NULL. No length is ever computed.

EX 7Merge two sorted lists using a dummy node

Medium

#include <stdio.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *merge(struct node *a, struct node *b) {
    struct node dummy = {0, NULL};
    struct node *tail = &dummy;
    while (a != NULL && b != NULL) {
        if (a->data <= b->data) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a != NULL ? a : b;
    return dummy.next;
}
 
int main(void) {
    struct node a3 = {7, NULL}, a2 = {4, &a3}, a1 = {1, &a2};
    struct node b4 = {10, NULL}, b3 = {9, &b4}, b2 = {3, &b3}, b1 = {2, &b2};
    for (struct node *p = merge(&a1, &b1); p != NULL; p = p->next) printf("%d ", p->data);
    printf("\n");
    return 0;
}

Output:

1 2 3 4 7 9 10

Reading it. The <= makes the merge stable: for equal keys, the node from the first list goes first. dummy is a sentinel: tail starts on it, so even the first node of the result is attached by the same statement tail->next = .... At each step the smaller of the two front nodes is relinked (no node is copied or allocated), and tail advances. When one list runs out, the rest of the other is attached in one assignment. The time is $O(m + n)$ and the extra space $O(1)$ . This is the merge step of merge sort, on a list.

EX 8What do these recursive list functions do?

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *range(int n) {
    struct node *head = NULL;
    for (int v = n; v >= 1; v--) {
        struct node *x = malloc(sizeof *x);
        if (x == NULL) exit(1);
        x->data = v;
        x->next = head;
        head = x;
    }
    return head;
}
 
static void f(struct node *p) {
    if (p == NULL) return;
    f(p->next);
    printf("%d ", p->data);
}
 
static struct node *pairs(struct node *h) {
    if (h == NULL || h->next == NULL) return h;
    struct node *second = h->next;
    h->next = pairs(second->next);
    second->next = h;
    return second;
}
 
int main(void) {
    struct node *h = range(5);
    f(h);
    printf("\n");
    for (struct node *p = pairs(h); p != NULL; p = p->next) printf("%d ", p->data);
    printf("\n");
    return 0;
}

Output:

5 4 3 2 1
2 1 4 3 5

f. The print comes after the recursive call, so the nodes are printed on the way back out of the recursion: the list in reverse order. Moving the printf before the call would print the list forwards. (It prints without changing the list.)

pairs. For h = node 1, second is node 2. The recursive call handles the list from node 3 onwards and returns its new head; that becomes h->next. Then second->next = h places node 1 after node 2. So each adjacent pair is swapped by relinking, and a lone last node (the 5) stays. To trace, solve the shortest case first (two nodes: 2, 1), then add a pair in front.

Cheat box

Delete cur with predecessor prev: prev->next = cur->next; free(cur);. First node: head = head->next; (save it before). Use struct node **pp = &head; to treat both cases alike.
Delete given only p (not last): copy p->next->data into p, then unlink p->next. Fails for the last node.
Reverse: save next; cur->next = prev; prev = cur; cur = next; finally head = prev. $O(n)$ time, $O(1)$ space.
Middle: slow by 1, fast by 2; loop while fast && fast->next. For an even length it returns the second middle.
$k$ -th from end: advance one pointer $k$ steps, then move both until the lead is NULL.
Cycle: slow/fast meet inside a cycle. Reset one to head, move both by 1: they meet at the cycle's first node.
Merge sorted lists: relink the smaller front node, with a dummy head: $O(m + n)$ .
Never use a node after free: save what you need (usually next) first. Also save next before overwriting it.

Traps and GATE patterns

Connections

Builds on

Singly linked lists

Unlocks

Singly linked listsuses Recursion patternsuses

Across subjects

Merge sortanalogous-to

Within this subject

Recursion patternsuses Stack (abstract data type)uses Dynamic memory: malloc, free and leaksuses

Reversal and the recursive printers rely on the call stack (recursion patterns, and the call stack). The merge routine is the heart of merge sort (sorting). A stack is a list where only the head changes. Leaks and dangling pointers from wrong rewiring are the subject of dynamic memory.

PYQs

7 previous year questions from your book. I re-solved each one myself (6 by running or simulating, 1 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · Set 1 · MCQQ1 · page 55 of the book

Consider the following code snippet in C language
that computes the number of nodes in a non-empty
singly linked list pointed to by the pointer variable
head.
struct node{
int elt;
struct node *next;
}
int getListSize (struct node *head)
{
if( El ) return 1;
return E2;
}
Which one of the following options gives the
correct replacements for the expressions E1 and
E2?

(a)E1: head == NULL E2: 1 + getListSize(head)
(b)E1: head->next == NULL E2: 1 + getListSize(head->next)
(c)E1: head == NULL E2: 1 + getListSize(head->next)
(d)E1: head->next == NULL E2: 1 + getListSize(head)

GATE 2025 · Set 1 · NATQ2 · page 55 of the book

Let LIST be a datatype for an implementation of
linked list defined as follows:
typedef struct list {
int data;
struct list *next;
} LIST;

Suppose the program has created two linked lists,
L1 and L2, whose contents are given in the figure
below (code for creating L1 and L2 is not
provided here). L1 contains 9 nodes, and L2
contains 7 nodes.
Consider the following C program segment that
modifies the list L1. The number of nodes in L1

int find (int query, LIST *list) {
while (list != NULL){
if(list->data == query) return 1;
list = list->next;
}
return 0;
}
int main () {
... ... ...
ptr1=L1; ptr2=L2;
while (ptr1->next != NULL){
query = ptr1->next->data;
if (find (query, L2))
ptr1->next = ptr1->next->next;
else ptr1 = ptr1->next;
}
... ... ...
return 0;
}

GATE 2021 · Set 2 · MCQ · 2 marksQ5 · page 56 of the book

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→va1ue = index;
boxE = boxN:

(a)It dereferences an uninitialized pointer that may result in a run-time error.
(b)It has a missing return which will be reported as an error by the compiler.
(c)Upon execution, the program creates a linked list of five nodes.
(d)Upon execution, the program goes into an infinite loop.

GATE 2020 · MCQ · 1 markQ6 · page 56 of the book

What is the worst case time complexity of inserting n
elements into an empty linked list, if the linked list
needs to be maintained in sorted order?

(a)Θ(n log n)
(b)Θ(n2 )
(c)Θ(1).
(d)Θ(n)

GATE 2017 · Set 1 · MCQQ8 · page 57 of the book

Consider the C code fragment given below.
typedef struct node {
int data;
node* next ;
} node;
void join (node* m, node* n) {
node* p=n ;
while (p->next ! =NULL){
p = p -> next ;
}
p-> next = m;
}
Assuming that m and n point to valid NULL-
terminated linked lists, invocation of join will

(a)append list m to the end of list n for all inputs.
(b)either cause a null pointer to dereference or append list m to the end of list n.
(c)cause a null pointer to dereference for all inputs.
(d)append list n to the end of list m for all inputs.

GATE 2010 · MCQ · 2 marksQ11 · page 57 of the book

The following C function takes a singly-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.
typedef struct node

{
int value;
struct node *next;
}Node;
Node *move_to_front(Node *head)
{
Node *p, *q;
if ((head == NULL: || (head->next == NULL))
return head;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
return head;
}

(a)q = NULL; p→next = head; head = p;
(b)q→next = NULL; head = p; p→next = head;
(c)head = p; p→next = q; q→next = NULL;
(d)q→next = NULL; p→next = head; head = p; DATA STRUCTURE

GATE 2008 · MCQ · 2 marksQ12 · page 58 of the book

The following C function takes a singly-linked list
of integers as a parameter and rearranges the
elements of the list. 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 || !list->next) return;

p = list;
q = list->next;
while (q) {
temp = p->value;
p->value = q->value;
q->value = temp;

p = q->next;
q = p ? p->next : 0;
}
}

(a)1,2,3,4,5,6,7
(b)2,1,4,3,6,5,7
(c)1,3,2,5,4,7,6
(d)2,3,4,5,6,7,1

Self-check

Question 1

What does this print?

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
int main(void) {
    struct node *h = NULL;
    for (int v = 6; v >= 1; v--) {
        struct node *x = malloc(sizeof *x);
        if (x == NULL) return 1;
        x->data = v;
        x->next = h;
        h = x;
    }
    for (struct node *p = h; p != NULL && p->next != NULL; p = p->next) {
        struct node *t = p->next;
        p->next = t->next;
        free(t);
    }
    for (struct node *p = h; p != NULL; p = p->next) printf("%d ", p->data);
    printf("\n");
    return 0;
}

Show answer

The list is 1 2 3 4 5 6. In each iteration p removes and frees the node after it, then moves on: it removes 2 (then p becomes 3), removes 4 (then p becomes 5), removes 6. The remaining list keeps every other node.

1 3 5

Question 2

In Floyd's method, why do the two pointers have to meet if there is a cycle?

Show answer

Once both are inside the cycle, each step moves fast one position further round than slow, so the distance between them (measured round the cycle) shrinks by exactly 1 per step. It must reach 0 within one cycle length, and then they are on the same node. With speeds 1 and 2 the gap never jumps over 0, because it changes by exactly 1 each step. (With other speed differences, such as 3 and 1, the gap changes by 2 and can skip over 0 for some cycle lengths.)

Question 3

You are given only a pointer p to a node in the middle of a singly linked list (no head). How do you delete it in $O(1)$ , and when does it fail?

Show answer

Copy the data of p->next into p, then unlink and free p->next. It fails if p is the last node (no next node), and any other pointer to the removed node (p->next before the operation) becomes dangling.

Question 4

What are the time and extra space of iterative and recursive reversal of an $n$ -node list?

Show answer

Both take $O(n)$ time. The iterative version uses $O(1)$ extra space (three pointers). The recursive version uses $O(n)$ extra space for the call stack, one frame per node.

Question 5

A function pre(p) prints p->data before calling pre(p->next), and a function post(p) prints after its recursive call. For the list 7, 8, 9, what do they print?

Show answer

pre prints on the way in: 7 8 9. post prints on the way out: 9 8 7.

Revision card

One-screen revision

Never touch a node after free: save next first. Save next before you overwrite it.
Delete: need the predecessor (or a struct node **). Head is a special case unless a dummy node or ** is used.
Delete with only a pointer to the node: copy the next node and unlink it. Not the last node.
Reverse: next = cur->next; cur->next = prev; prev = cur; cur = next; $O(n)$ time, $O(1)$ space.
Middle: slow 1, fast 2, guard fast && fast->next. $k$ -th from end: gap of $k$ .
Floyd: meet inside a cycle; reset one pointer to the head, move both by 1 to find the cycle start.
Merge: relink the smaller front node, dummy head, $O(m + n)$ .
Print before the call: forward. Print after the call: reverse.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 10.2 Linked lists (including the sentinel idea)
·Kernighan and Ritchie, The C Programming Language, 2nd ed., Sections 5.1 Pointers and Addresses, 6.5 Self-referential Structures

Verification

The two animations replay real runs of instrumented C programs: every address, data value and next pointer is read from the heap nodes at each step, the leak flags are computed by following pointers from the live variables, and the test suite checks that unlinking happens before the free, that every node stays reachable during the reversal, and the final orders. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan (with leak detection off: several examples do not free their lists to stay short). The textbook section numbers were written from memory and have NOT been checked against the books. The prose, the cycle-start argument and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Singly linked lists

Recursion and the call stack