Linked Lists
Linked List Problems
The classic interview and exam problems: reverse a list, find the middle, detect a cycle with Floyd's algorithm, merge two sorted lists and remove duplicates.
These problems appear constantly in CSE 102 exams and placement interviews. Each uses a small trick with pointers. All of them use this node type and helper:
typedef struct Node { int data; struct Node *next; } Node;Reverse a linked list
Walk the list once, turning each next pointer around. Keep three pointers: prev, cur and next.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int data; struct Node *next; } Node;
Node *build(const int *a, int n) {
Node *head = NULL, **tail = &head;
for (int i = 0; i < n; i++) {
*tail = malloc(sizeof(Node));
(*tail)->data = a[i];
(*tail)->next = NULL;
tail = &(*tail)->next;
}
return head;
}
void print(const Node *h) { for (; h; h = h->next) printf("%d ", h->data); printf("\n"); }
Node *reverse(Node *head) {
Node *prev = NULL, *cur = head;
while (cur != NULL) {
Node *next = cur->next; // 1. remember the rest
cur->next = prev; // 2. turn this pointer around
prev = cur; // 3. step forward
cur = next;
}
return prev; // prev is the new head
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
Node *head = build(a, 5);
print(head);
head = reverse(head);
print(head);
return 0;
}1 2 3 4 5 5 4 3 2 1
It runs in O(n) time and O(1) extra space. The recursive version is shorter but uses O(n) stack space:
Node *reverseRec(Node *head) {
if (head == NULL || head->next == NULL) return head;
Node *rest = reverseRec(head->next);
head->next->next = head; // the node after head now points back
head->next = NULL;
return rest;
}Find the middle: slow and fast pointers
Move slow one step and fast two steps at a time. When fast reaches the end, slow is in the middle — one pass, no counting.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int data; struct Node *next; } Node;
Node *push(Node *head, int v) { Node *n = malloc(sizeof(Node)); n->data = v; n->next = head; return n; }
int middle(Node *head) {
Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow->data;
}
int main(void) {
Node *odd = NULL, *even = NULL;
for (int v = 5; v >= 1; v--) odd = push(odd, v); // 1 2 3 4 5
for (int v = 6; v >= 1; v--) even = push(even, v); // 1 2 3 4 5 6
printf("middle of 1..5 = %d\n", middle(odd));
printf("middle of 1..6 = %d\n", middle(even)); // second of the two middles
return 0;
}middle of 1..5 = 3 middle of 1..6 = 4
Detect a cycle: Floyd's tortoise and hare
If a bug makes some node point back to an earlier one, traversal loops forever. Floyd's algorithm uses the same slow/fast idea: in a cycle, the fast pointer eventually laps the slow one and they meet.
slow and fast must meet inside the loop.#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int data; struct Node *next; } Node;
int hasCycle(Node *head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return 1;
}
return 0;
}
int main(void) {
Node n[5];
for (int i = 0; i < 5; i++) { n[i].data = i + 1; n[i].next = (i < 4) ? &n[i + 1] : NULL; }
printf("straight list has cycle? %s\n", hasCycle(&n[0]) ? "yes" : "no");
n[4].next = &n[1]; // 5 -> 2 creates a loop
printf("after 5 -> 2, has cycle? %s\n", hasCycle(&n[0]) ? "yes" : "no");
return 0;
}straight list has cycle? no after 5 -> 2, has cycle? yes
Time O(n), space O(1). (A simpler approach stores visited nodes in a hash set, but that costs O(n) memory.)
Merge two sorted lists
Repeatedly take the smaller head. A dummy node avoids special-casing the first element:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int data; struct Node *next; } Node;
Node *fromArray(const int *a, int n) {
Node *head = NULL;
for (int i = n - 1; i >= 0; i--) { Node *x = malloc(sizeof(Node)); x->data = a[i]; x->next = head; head = x; }
return head;
}
void print(const Node *h) { for (; h; h = h->next) printf("%d ", h->data); printf("\n"); }
Node *merge(Node *a, Node *b) {
Node dummy = {0, NULL}, *tail = &dummy;
while (a && b) {
if (a->data <= b->data) { tail->next = a; a = a->next; }
else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = a ? a : b; // attach whatever is left
return dummy.next;
}
int main(void) {
int x[] = {2, 7, 9, 15}, y[] = {1, 3, 8, 20, 21};
print(merge(fromArray(x, 4), fromArray(y, 5)));
return 0;
}1 2 3 7 8 9 15 20 21
Remove duplicates from a sorted list
In a sorted list, duplicates sit next to each other, so one pass suffices:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
int a[] = {1, 1, 2, 3, 3, 3, 4, 5, 5};
Node *head = NULL;
for (int i = 8; i >= 0; i--) { Node *x = malloc(sizeof(Node)); x->data = a[i]; x->next = head; head = x; }
for (Node *p = head; p && p->next; ) {
if (p->data == p->next->data) {
Node *dup = p->next;
p->next = dup->next;
free(dup);
} else p = p->next;
}
for (Node *p = head; p; p = p->next) printf("%d ", p->data);
printf("\n");
return 0;
}1 2 3 4 5
Test yourself
4 questions · pick an answer to check it instantly
- 1
In iterative reversal, which pointer becomes the new head?
WhencurbecomesNULL,prevpoints at the old last node, which is the new first node. - 2
In Floyd's cycle detection, how fast do the two pointers move?
The fast pointer gains one node per round, so it must meet the slow one inside a cycle. - 3
What extra space does Floyd's algorithm use?
Just two pointers, regardless of list length. - 4
How can you find the 3rd node from the end in one pass?
The gap of 3 is kept, so when the lead pointer runs off the end, the trailing pointer is 3 from the end.