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

Linked List का Middle ढूँढना

बीच का ढूंढना एक slow और एक fast walker उपयोग करता है: जब fast वाला एक समय में दो steps लेकर आखिर तक पहुंचता है, slow वाला बीच में खड़ा होता है।

In this page:

  1. Problem
  2. Slow and Fast
  3. Finding the Middle
  4. Why It Works
  5. Complexity
Syntax
markup 
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow    # middle node

Problem

किसी linked list का बीच वाला node ढूंढना कई दूसरे algorithms में एक building block के रूप में आता है, जैसे merge sort के लिए एक list को आधे में split करना या यह जांचना कि कोई list palindrome है या नहीं।

उदाहरण: Problem

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, new Node{2, new Node{3, new Node{4, new Node{5, nullptr}}}}};
    cout << "finding the middle helps split a list for merge sort or palindrome checks" << 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); a.next = new Node(2); a.next.next = new Node(3);
        System.out.println("finding the middle helps split a list for merge sort or palindrome checks");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a = Node(1); a.next = Node(2); a.next.next = Node(3)
print("finding the middle helps split a list for merge sort or palindrome checks")
#include <stdio.h>
int main() {
    printf("finding the middle helps split a list for merge sort or palindrome checks\n");
    return 0;
}

Slow and Fast

Efficient approach अलग speeds पर move होते दो pointers उपयोग करता है: एक slow pointer जो per step एक node advance करता है, और एक fast pointer जो per step दो nodes advance करता है, दोनों head से शुरू होते हुए।

उदाहरण: Slow and Fast

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{1, new Node{2, new Node{3, new Node{4, new Node{5, nullptr}}}}};
    Node* slow = head; Node* fast = head;
    cout << "slow starts at " << slow->data << ", fast starts at " << fast->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 head = new Node(1); head.next = new Node(2);
        Node slow = head, fast = head;
        System.out.println("slow starts at " + slow.data + ", fast starts at " + fast.data);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1); head.next = Node(2)
slow = fast = head
print("slow starts at", slow.data, ", fast starts at", fast.data)
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *head = malloc(sizeof(struct Node)); head->data = 1;
    struct Node *slow = head, *fast = head;
    printf("slow starts at %d, fast starts at %d\n", slow->data, fast->data);
    return 0;
}

Finding the Middle

जब तक fast pointer list के आखिर तक पहुंचता है, slow pointer, बिल्कुल आधी distance cover करके, बिल्कुल middle node पर बैठा है, किसी अलग length calculation की ज़रूरत नहीं।

उदाहरण: Finding the Middle

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* head = new Node{1, new Node{2, new Node{3, new Node{4, new Node{5, nullptr}}}}};
    Node* slow = head; Node* fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    cout << "middle node: " << slow->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 head = new Node(1); head.next = new Node(2); head.next.next = new Node(3);
        head.next.next.next = new Node(4); head.next.next.next.next = new Node(5);
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        System.out.println("middle node: " + slow.data);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2); head.next.next = Node(3)
head.next.next.next = Node(4); head.next.next.next.next = Node(5)
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
print("middle node:", slow.data)
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *n5 = malloc(sizeof(struct Node)); n5->data = 5; n5->next = NULL;
    struct Node *n4 = malloc(sizeof(struct Node)); n4->data = 4; n4->next = n5;
    struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = n4;
    struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
    struct Node *head = malloc(sizeof(struct Node)); head->data = 1; head->next = n2;
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    printf("middle node: %d\n", slow->data);
    return 0;
}

Why It Works

यह काम करता है क्योंकि fast pointer हमेशा steps की उतनी ही संख्या में slow pointer से दोगुनी distance cover करता है, इसलिए जब fast ने पूरी length travel की हो, slow ने बिल्कुल इसका आधा travel किया है।

उदाहरण: Why It Works

#include <iostream>
using namespace std;
int main() {
    int steps = 0;
    for (int fastPos = 0; fastPos < 5; fastPos += 2) steps++;
    cout << "fast moves 2x speed of slow, so when fast covers full length, slow is at half: " << steps << " steps" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int steps = 0;
        for (int fastPos = 0; fastPos < 5; fastPos += 2) steps++;
        System.out.println("fast moves 2x speed of slow, so when fast covers full length, slow is at half: " + steps + " steps");
    }
}
steps = 0
fast_pos = 0
while fast_pos < 5:
    fast_pos += 2
    steps += 1
print("fast moves 2x speed of slow, so when fast covers full length, slow is at half:", steps, "steps")
#include <stdio.h>
int main() {
    int steps = 0;
    for (int fastPos = 0; fastPos < 5; fastPos += 2) steps++;
    printf("fast moves 2x speed, slow ends at half: %d steps\n", steps);
    return 0;
}

Complexity

यह slow/fast pointer approach list में एक single O(n) pass में बीच ढूंढता है, सिर्फ O(1) extra space उपयोग करते हुए, एक two-pass approach की तुलना में जो पहले length count करती और फिर midpoint तक चलती।

उदाहरण: Complexity

#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* slow = head; Node* fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    cout << "found middle (" << slow->data << ") in one O(n) pass, O(1) space" << endl;
    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 slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        System.out.println("found middle (" + slow.data + ") in one O(n) pass, O(1) space");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1); head.next = Node(2); head.next.next = Node(3)
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
print("found middle (", slow.data, ") in one O(n) pass, O(1) space")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = NULL;
    struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
    struct Node *head = malloc(sizeof(struct Node)); head->data = 1; head->next = n2;
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    printf("found middle (%d) in O(n) pass, O(1) space\n", slow->data);
    return 0;
}
Related Topics

Linked List को Reverse करना · Circular Linked List क्या है · Doubly Linked List क्या है · Singly Linked List क्या है

{# 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. while (fast->next && fast->next->next) बनाम while (fast && fast->next) से loop करना यह notice किए बिना कि वे even-length lists के लिए अलग middles return करते हैं।
  2. fast के nullptr होने पर fast->next dereference करना, जो empty या short lists पर crash करता है।
  3. पहले nodes count करना और फिर फिर चलना, जो काम करता है लेकिन दो passes चाहता है जब slow/fast को सिर्फ एक चाहिए।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Merge Two Sorted Lists Next Lesson → Remove Nth Node from End

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.