← Back to DSA Course | Chapter 4: Linked Lists | Lesson 4 of 8

Linked List को Reverse करना

एक linked list को reverse करना एक line में हाथ पकड़े हर kid को घूमने और जो उनके पीछे था उसका हाथ पकड़ने को कहने जैसा है।

In this page:

  1. Idea of Reversal
  2. Iterative Method
  3. Pointer Steps
  4. Result
  5. Complexity
Syntax
markup 
prev = None
current = head
while current:
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
head = prev

Idea of Reversal

किसी linked list को reverse करने का मतलब है हर node के next pointer को flip करना ताकि यह उस node की ओर point करे जो इससे पहले आया बजाय उसके जो बाद में आया, जो effectively पूरी chain को घुमा देता है।

उदाहरण: Idea of Reversal

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr};
    Node* b = new Node{2, nullptr};
    Node* c = new Node{3, nullptr};
    a->next = b; b->next = c;
    cout << "before: " << a->data << "->" << b->data << "->" << c->data << endl;
    c->next = b; b->next = a; a->next = nullptr;
    cout << "after: " << c->data << "->" << b->data << "->" << a->data << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.next = c;
        System.out.println("before: " + a.data + "->" + b.data + "->" + c.data);
        c.next = b; b.next = a; a.next = null;
        System.out.println("after: " + c.data + "->" + b.data + "->" + a.data);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
print("before:", a.data, "->", b.data, "->", c.data)
c.next = b
b.next = a
a.next = None
print("after:", c.data, "->", b.data, "->", a.data)
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    struct Node *c = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2; c->data = 3;
    a->next = b; b->next = c; c->next = NULL;
    printf("before: %d->%d->%d\n", a->data, b->data, c->data);
    c->next = b; b->next = a; a->next = NULL;
    printf("after: %d->%d->%d\n", c->data, b->data, a->data);
    return 0;
}

Iterative Method

Iterative method list में एक बार चलता है, और हर node पर इसके next pointer को पिछले node की ओर पीछे point करने के लिए redirect करता है, पहले अगले node का एक reference carefully save करते हुए ताकि list का बाकी हिस्सा न खो जाए।

उदाहरण: Iterative Method

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* reverseList(Node* head) {
    Node* prev = nullptr;
    while (head != nullptr) {
        Node* nextNode = head->next;
        head->next = prev;
        prev = head;
        head = nextNode;
    }
    return prev;
}
int main() {
    Node* a = new Node{1, new Node{2, new Node{3, nullptr}}};
    Node* newHead = reverseList(a);
    for (Node* c = newHead; c; c = c->next) cout << c->data << " ";
    cout << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static Node reverseList(Node head) {
        Node prev = null;
        while (head != null) {
            Node nextNode = head.next;
            head.next = prev;
            prev = head;
            head = nextNode;
        }
        return prev;
    }
    public static void main(String[] args) {
        Node a = new Node(1); a.next = new Node(2); a.next.next = new Node(3);
        Node newHead = reverseList(a);
        for (Node c = newHead; c != null; c = c.next) System.out.print(c.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse_list(head):
    prev = None
    while head is not None:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node
    return prev

a = Node(1); a.next = Node(2); a.next.next = Node(3)
new_head = reverse_list(a)
c = new_head
while c:
    print(c.data, end=" ")
    c = c.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* reverseList(struct Node *head) {
    struct Node *prev = NULL;
    while (head != NULL) {
        struct Node *nextNode = head->next;
        head->next = prev;
        prev = head;
        head = nextNode;
    }
    return prev;
}
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = b; b->next = c;
    struct Node *newHead = reverseList(a);
    for (struct Node *n = newHead; n; n = n->next) printf("%d ", n->data);
    printf("\n");
    return 0;
}

Pointer Steps

तीन pointers logic को manageable बनाते हैं: एक पिछले node के लिए, एक process हो रहे current node के लिए, और एक temporary pointer current का pointer overwrite करने से पहले अगला node याद रखने के लिए।

उदाहरण: Pointer Steps

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{1, new Node{2, new Node{3, nullptr}}};
    Node* prevNode = nullptr;
    Node* curr = head;
    while (curr != nullptr) {
        Node* nextNode = curr->next;
        cout << "curr=" << curr->data << " prev=" << (prevNode ? to_string(prevNode->data) : "null") << endl;
        curr->next = prevNode;
        prevNode = curr;
        curr = nextNode;
    }
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3);
        Node prevNode = null, curr = head;
        while (curr != null) {
            Node nextNode = curr.next;
            System.out.println("curr=" + curr.data + " prev=" + (prevNode == null ? "null" : prevNode.data));
            curr.next = prevNode;
            prevNode = curr;
            curr = nextNode;
        }
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1); head.next = Node(2); head.next.next = Node(3)
prev_node, curr = None, head
while curr is not None:
    next_node = curr.next
    print("curr=", curr.data, "prev=", prev_node.data if prev_node else "None")
    curr.next = prev_node
    prev_node = curr
    curr = next_node
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = b; b->next = c;
    struct Node *prevNode = NULL, *curr = a;
    while (curr != NULL) {
        struct Node *nextNode = curr->next;
        printf("curr=%d prev=%d\n", curr->data, prevNode ? prevNode->data : -1);
        curr->next = prevNode;
        prevNode = curr;
        curr = nextNode;
    }
    return 0;
}

Result

एक बार reversal खत्म हो जाए, वह node जो कभी tail था (एक null next pointer के साथ) अब list का head है, क्योंकि यह आखिरी process किया गया node था और इसका next pointer second-to-last node की ओर point करने के लिए सेट था।

उदाहरण: Result

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* reverseList(Node* head) {
    Node* prev = nullptr;
    while (head) { Node* nx = head->next; head->next = prev; prev = head; head = nx; }
    return prev;
}
int main() {
    Node* a = new Node{1, new Node{2, new Node{3, nullptr}}};
    Node* oldTail = a;
    while (oldTail->next) oldTail = oldTail->next;
    Node* newHead = reverseList(a);
    cout << "old tail is now head: " << (newHead == oldTail) << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static Node reverseList(Node head) {
        Node prev = null;
        while (head != null) { Node nx = head.next; head.next = prev; prev = head; head = nx; }
        return prev;
    }
    public static void main(String[] args) {
        Node a = new Node(1); a.next = new Node(2); a.next.next = new Node(3);
        Node oldTail = a;
        while (oldTail.next != null) oldTail = oldTail.next;
        Node newHead = reverseList(a);
        System.out.println("old tail is now head: " + (newHead == oldTail));
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse_list(head):
    prev = None
    while head:
        nx = head.next
        head.next = prev
        prev = head
        head = nx
    return prev

a = Node(1); a.next = Node(2); a.next.next = Node(3)
old_tail = a
while old_tail.next:
    old_tail = old_tail.next
new_head = reverse_list(a)
print("old tail is now head:", new_head is old_tail)
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* reverseList(struct Node *head) {
    struct Node *prev = NULL;
    while (head) { struct Node *nx = head->next; head->next = prev; prev = head; head = nx; }
    return prev;
}
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = b; b->next = c;
    struct Node *oldTail = a;
    while (oldTail->next) oldTail = oldTail->next;
    struct Node *newHead = reverseList(a);
    printf("old tail is now head: %d\n", newHead == oldTail);
    return 0;
}

Complexity

Iterative approach पूरी list को एक single O(n) pass में reverse करता है सिर्फ pointer variables का एक fixed handful उपयोग करते हुए, इसलिए इसे O(1) extra space चाहिए, एक recursive version के विपरीत जो O(n) stack space उपयोग करता है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
Node* reverseList(Node* head) {
    Node* prev = nullptr;
    while (head) { Node* nx = head->next; head->next = prev; prev = head; head = nx; }
    return prev;
}
int main() {
    Node* a = new Node{1, new Node{2, new Node{3, nullptr}}};
    Node* r = reverseList(a);
    cout << "reversed in O(n) time, O(1) extra space (just prev/curr/next pointers)" << endl;
    for (Node* c = r; c; c = c->next) cout << c->data << " ";
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static Node reverseList(Node head) {
        Node prev = null;
        while (head != null) { Node nx = head.next; head.next = prev; prev = head; head = nx; }
        return prev;
    }
    public static void main(String[] args) {
        Node a = new Node(1); a.next = new Node(2); a.next.next = new Node(3);
        Node r = reverseList(a);
        System.out.println("reversed in O(n) time, O(1) extra space (just prev/curr/next pointers)");
        for (Node c = r; c != null; c = c.next) System.out.print(c.data + " ");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse_list(head):
    prev = None
    while head:
        nx = head.next
        head.next = prev
        prev = head
        head = nx
    return prev

a = Node(1); a.next = Node(2); a.next.next = Node(3)
r = reverse_list(a)
print("reversed in O(n) time, O(1) extra space (just prev/curr/next pointers)")
c = r
while c:
    print(c.data, end=" ")
    c = c.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node* reverseList(struct Node *head) {
    struct Node *prev = NULL;
    while (head) { struct Node *nx = head->next; head->next = prev; prev = head; head = nx; }
    return prev;
}
int main() {
    struct Node *a = malloc(sizeof(struct Node)); a->data = 1;
    struct Node *b = malloc(sizeof(struct Node)); b->data = 2;
    struct Node *c = malloc(sizeof(struct Node)); c->data = 3; c->next = NULL;
    a->next = b; b->next = c;
    struct Node *r = reverseList(a);
    printf("reversed in O(n) time, O(1) extra space\n");
    for (struct Node *n = r; n; n = n->next) printf("%d ", n->data);
    return 0;
}
Related Topics

Circular Linked List क्या है · Doubly Linked List क्या है · Singly Linked List क्या है · Linked List का Middle ढूँढना

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. अगला node save करने से पहले curr->next overwrite करना, इसलिए list का बाकी हिस्सा खो जाता है।
  2. आखिर में prev के बजाय पुराना head return करना, जो नया head है।
  3. पुराने head का next nullptr सेट करना भूल जाना, जो एक cycle या गलत tail छोड़ देता है।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Circular Linked List Next Lesson → Floyds Cycle Detection

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.