📘 Lesson · Lesson 65

Reverse Linked List

Q: C में linked list कैसे reverse करते हैं?

मानक iterative तरीका तीन pointers इस्तेमाल करता है — prev, current और next। आप list में एक बार चलते हैं, और हर node के लिए उसका next सहेजते हैं, node को prev की ओर पीछे point कराते हैं, फिर prev और current आगे बढ़ाते हैं। खत्म होने पर prev नया head होता है।

Q: Linked list reverse करने के लिए तीन pointers क्यों चाहिए?

क्योंकि जब आप किसी node का next pointer पीछे की ओर पलटते हैं, तो बाकी list का link खो जाता है। इसे पहले एक next pointer में सहेजना यह नुकसान रोकता है, prev पहले से पलटा हिस्सा रखता है, और current वह node है जिसे आप पलट रहे हैं। तीनों एक साथ चाहिए।

Written and reviewed by Gagan Bhardwaj · Senior IT Faculty · 15+ years’ experience

लक्ष्य: links पलटना

Linked list reverse करने का मतलब उसे उल्टी दिशा में चलाना: list 1 → 2 → 3 बन जाती है 3 → 2 → 1। हम data इधर-उधर नहीं करते — बल्कि हर node का next pointer पलटते हैं ताकि वह अगले के बजाय पिछले node की ओर इशारा करे।

अगर linked lists नई हैं तो पहले C में linked list पढ़ें। यहाँ हम classic तीन-pointer reversal पर ध्यान देते हैं।

तीन-pointer विचार

List में एक बार चलते हुए हम तीन pointers रखते हैं:

Pointer	इसका काम
`prev`	पहले से पलटा हिस्सा (`NULL` से शुरू)
`current`	वह node जिसे अभी पलट रहे हैं
`next`	पलटने से पहले बाकी list सहेजता है

Links कैसे पलटते हैं, कदम-दर-कदम

हर node के लिए, चार छोटे कदम क्रम में होते हैं:

चार कदम

1. next = current->next;   // aage ka save karein
2. current->next = prev;   // link peeche palten
3. prev = current;         // prev aage badhayein
4. current = next;         // current aage badhayein

कदम 1 कुंजी है — next सहेजे बिना, कदम 2 में link पलटने से बाकी list छूट जाती।

पूरा program

C Language

#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };

struct Node* reverse(struct Node *head) {
    struct Node *prev = NULL, *current = head, *next = NULL;
    while (current != NULL) {
        next = current->next;    // 1. aage save
        current->next = prev;    // 2. flip
        prev = current;          // 3. prev aage
        current = next;          // 4. current aage
    }
    return prev;                 // naya head
}
void printList(struct Node *n) {
    while (n) { printf("%d -> ", n->data); n = n->next; }
    printf("NULL\n");
}
struct Node* newNode(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = v; n->next = NULL; return n;
}
int main() {
    struct Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);

    printf("Original: "); printList(head);
    head = reverse(head);
    printf("Reversed: "); printList(head);
    return 0;
}

Output:
Original: 1 -> 2 -> 3 -> NULL
Reversed: 3 -> 2 -> 1 -> NULL

Dry run

कदम	prev	current	अब तक (पलटा हिस्सा)
शुरू	NULL	1	—
node 1 के बाद	1	2	1 → NULL
node 2 के बाद	2	3	2 → 1 → NULL
node 3 के बाद	3	NULL	3 → 2 → 1 → NULL

जब current NULL पर पहुँचता है, prev (node 3) नया head होता है।

आम गलतियाँ

पलटने से पहले next न सहेजना — आप बाकी list खो देते हैं।
prev को नया head लौटाना भूलना (पुराना head लौटाने से सिर्फ़ एक node मिलता है)।
prev को NULL के बजाय head से शुरू करना।
चार कदम गलत क्रम में करना।

🏋️ अभ्यास

List में चौथा node (4) जोड़ें और पुष्टि करें कि reversed output 4 → 3 → 2 → 1 → NULL है। फिर recursive version लिखने की कोशिश करें और तुलना करें।

सारांश

Reversing हर node के next को पीछे की ओर पलटता है।
तीन pointers इस्तेमाल करें: prev, current, next।
Current link पलटने से पहले हमेशा next सहेजें।
अंत में prev लौटाएँ — यही नया head है।
O(n) time और O(1) अतिरिक्त space में चलता है।

अक्सर पूछे जाने वाले प्रश्न (FAQ)

C में linked list कैसे reverse करते हैं?

मानक iterative तरीका तीन pointers इस्तेमाल करता है — prev, current और next। आप list में एक बार चलते हैं, और हर node के लिए उसका next सहेजते हैं, node को prev की ओर पीछे point कराते हैं, फिर prev और current आगे बढ़ाते हैं। खत्म होने पर prev नया head होता है।

Linked list reverse करने के लिए तीन pointers क्यों चाहिए?

क्योंकि जब आप किसी node का next pointer पीछे की ओर पलटते हैं, तो बाकी list का link खो जाता है। इसे पहले एक next pointer में सहेजना यह नुकसान रोकता है, prev पहले से पलटा हिस्सा रखता है, और current वह node है जिसे आप पलट रहे हैं। तीनों एक साथ चाहिए।

Linked list reverse करने की time complexity क्या है?

Iterative reversal O(n) time में चलता है क्योंकि यह हर node को ठीक एक बार देखता है, और O(1) अतिरिक्त space इस्तेमाल करता है क्योंकि list size चाहे जो हो, उसे सिर्फ़ तीन pointer variables चाहिए। यह इसे तेज़ और memory-कुशल दोनों बनाता है।

Reverse करने के बाद head किस ओर इशारा करता है?

पूरे reversal के बाद, मूल आख़िरी node नया head बन जाता है, और मूल पहला node आख़िरी बन जाता है, जिसका next NULL होता है। तो आप अपने head pointer को उस पर update करते हैं जो loop के अंत में prev था।

क्या recursion से linked list reverse कर सकते हैं?

हाँ। Recursive version पहले बाकी list पर खुद को call करता है, फिर लौटते समय links ठीक करता है ताकि हर node अपने पिछले की ओर इशारा करे। यह सुंदर है पर O(n) stack space इस्तेमाल करता है, जबकि iterative तीन-pointer तरीका सिर्फ़ O(1) इस्तेमाल करता है।

← Back to C Tutorial

💻 लाइव कोड एडिटर

इस पेज के प्रोग्राम यहीं तैयार हैं — चलाएँ, बदलें और सीखें। कुछ भी इंस्टॉल किए बिना।

OneCompiler द्वारा संचालित। कोड एडिटर में अपने आप आ जाता है — Run दबाकर आउटपुट देखें। अगर एडिटर न खुले तो नए टैब में खोलें.