Linked-list questions in GATE rarely stop at a definition. They present a C fragment and ask for the output, the final list, or the purpose of a function. The difficult part is not syntax. It is preserving the remaining list while two or three pointers are being moved.
The safest method is to draw the nodes, update one statement at a time, and never assume an arrow that the code has not assigned. Exact node values keep every pointer change visible.
The node and two rules that never change
A singly linked-list node stores data and a pointer to the next node. head identifies the first node, and the last node's next is NULL.
struct Node {
int data;
struct Node *next;
};Two rules control nearly every manipulation question.
Save a link before overwriting it. If
curr->nextis the only route to the rest of the list, store that pointer before changingcurr->next.Verify all affected arrows and head. An operation is complete only when each changed
nextpoints to the correct node andheadreaches the new first node.
This is easier if you separate pointer variables from nodes. curr is a variable that points to a node. Changing curr does not move or copy that node. Changing curr->next rewires an arrow stored inside it. The memory pictures in Pointers in C for GATE reinforce that distinction.
Iterative reversal traced node by node
Reverse this list:
10 -> 20 -> 30 -> 40 -> NULL
The standard loop is:
prev = NULL;
curr = head;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;Trace the four variables after every iteration. At the start, prev = NULL, curr = 10, and head = 10.
Iteration 1
Save next = 20. Rewire 10->next = NULL. Move prev to 10 and curr to the saved node 20.
The reversed part is 10 -> NULL. The unprocessed part still begins at 20.
Iteration 2
Save next = 30. Rewire 20->next = 10. Set prev = 20 and curr = 30.
The reversed part is now 20 -> 10 -> NULL.
Iteration 3
Save next = 40. Rewire 30->next = 20. Set prev = 30 and curr = 40.
The reversed part is 30 -> 20 -> 10 -> NULL.
Iteration 4
Save next = NULL. Rewire 40->next = 30. Set prev = 40 and curr = NULL.
The loop stops because curr is NULL. Finally set head = prev, so head points to 40. The result is:
40 -> 30 -> 20 -> 10 -> NULL
The statement order is essential. If curr->next = prev runs before next = curr->next, the original forward link is gone. After the first iteration, there is then no pointer left through which the loop can reach 20, 30, or 40.
Slow and fast pointers for the middle
Now use this five-node list:
10 -> 20 -> 30 -> 40 -> 50 -> NULL
Set both pointers to head. On each loop iteration, move slow by one link and fast by two. Continue while both fast and fast->next are non-NULL.
Position | slow | fast |
|---|---|---|
Start | 10 | 10 |
After step 1 | 20 | 30 |
After step 2 | 30 | 50 |
At node 50, fast->next is NULL, so the loop stops. slow points to 30, the middle node.
For an even number of nodes, the loop condition controls which middle you obtain. With the condition above on 10 -> 20 -> 30 -> 40, the pointers move to slow = 20, fast = 30, then to slow = 30, fast = NULL. The result is 30, the second of the two middle nodes. If a question expects the first middle, adjust the stopping condition rather than silently changing the answer.
Floyd's cycle test traced on a list that loops back
The same speed difference detects a loop. Keep the same five nodes, but make 50 point back to 30 instead of NULL, so 30, 40 and 50 form a cycle:
10 -> 20 -> 30 -> 40 -> 50 -> back to 30
Start slow and fast at head again and take the same one-link and two-link steps.
Step | slow | fast |
|---|---|---|
Start | 10 | 10 |
After step 1 | 20 | 30 |
After step 2 | 30 | 50 |
After step 3 | 40 | 40 |
After step 3 both pointers hold node 40, so the list contains a cycle. Without the back link, fast would have run out of nodes and the loop would have ended with no match, which is what happened on the straight five-node list above.
The meeting node is not the start of the loop. Leave one pointer at 40, restart the other at head, and move both one link at a time: 10 and 40, then 20 and 50, then 30 and 30. They meet at 30, which is the first node of the cycle.
Deletion and the sentinel idea
To delete a middle node called target, you normally need its predecessor:
prev->next = target->next
Deleting the first node is different because there is no predecessor. Set head = head->next, then release the old head if the language and question require memory management.
A dummy or sentinel node removes that special case. Make the dummy's next point to the real head, begin traversal at the dummy, and perform the same predecessor-based update whether the target is first or later. The real head after deletion is dummy.next.
There is also a familiar interview and exam variation: delete a node when only a pointer to that node is given. Copy the next node's data into the current node, then bypass the next node. This works for any node except the last one. A last node has no successor whose data and link can be copied.
Traps GATE plants in code
When tracing a snippet, check these points before you execute a single line in your head:
Statement order: saving
nextafter rewiring loses the original tail.NULL safety:
head = NULLand a single-node list can make an unchecked dereference fail.Head update: after reversal,
previs the new first node. Returning the oldheadreturns the last node of the reversed chain.Middle convention: an even-length list has two central nodes, and the loop guard decides which one is returned.
Pointer versus data: copying
datadoes not move a node, and moving a pointer does not copy data.
Stacks and queues are often implemented through the same link changes. Stacks and Queues Explained is a useful next comparison because push, pop, enqueue, and dequeue all reduce to controlled head or tail updates.
How GATE asks the topic
Typical stems ask for the output of a function, the final list after several assignments, the value of a pointer after k iterations, the number of visited nodes, or what a short function accomplishes. Draw the actual values from the stem and execute one assignment per line. Do not repair suspicious code in your head.
A worked question on statement order
A stem gives the list 10 -> 20 -> 30 -> 40 and this loop, and asks what the list contains when the loop ends.
prev = NULL;
curr = head;
while (curr != NULL) {
curr->next = prev;
next = curr->next;
prev = curr;
curr = next;
}
head = prev;The two assignments inside the loop have been swapped. Execute them literally. First pass: curr->next = prev sets 10->next to NULL, so the only route to 20 is gone. next = curr->next then reads the arrow that was just overwritten, so next is NULL. prev becomes 10 and curr becomes NULL.
curr is NULL, so the loop ends after one pass and head = prev leaves head on 10. The answer is the one-node list 10 -> NULL. Nodes 20, 30 and 40 are still in memory but nothing points to them. The correct loop, which saves next first, returns 40 -> 30 -> 20 -> 10 -> NULL.
For current subject weightage and paper pattern, confirm against the official GATE portal of the organising IIT. The pointer patterns remain stable. KnowledgeGate carries more than 1,500 Data Structure questions, over 140 of them on linked lists, covering reversal, deletion, merge, and traversal drills.
Short version and next step
Save next before rewiring, track prev, curr, and next literally, and use slow and fast pointers when a question asks about a middle or cycle. After every operation, verify the arrow stored in each affected node and verify head separately.
Build that reflex through the pointer walkthroughs in GATE Guidance by Sanchit Sir and timed Data Structure sets in the GATE Test Series. Use the GATE category to move from linked lists into neighbouring linear structures once the trace feels routine.
