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

End से Nth Node हटाना

आखिर से nth node हटाना एक friend को n steps आगे भेजने जैसा है, इसलिए जब वे आखिर तक पहुंचते हैं, दूसरा बिल्कुल वहीं है जहां आपको snip करना है।

In this page:

  1. Problem
  2. Two Pointer Method
  3. Remove Node
  4. Dummy Node
  5. Complexity
Syntax
markup 
dummy = Node(0)
dummy.next = head
fast = slow = dummy
for _ in range(n):
    fast = fast.next
while fast.next:
    fast = fast.next
    slow = slow.next
slow.next = slow.next.next

Problem

यह problem आपसे एक linked list के आखिर से n positions वाला node हटाने को कहती है, एक single pass में, पहले एक अलग traversal में list की total length count किए बिना।

उदाहरण: Problem

#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, nullptr}}}};
    cout << "remove the 2nd node from the end, in a single pass, n=2" << 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);
        System.out.println("remove the 2nd node from the end, in a single pass, n=2");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1); head.next = Node(2)
print("remove the 2nd node from the end, in a single pass, n=2")
#include <stdio.h>
int main() {
    printf("remove the 2nd node from the end, in a single pass, n=2\n");
    return 0;
}

Two Pointer Method

एक two-pointer technique इसे elegantly solve करती है: पहले एक pointer को दूसरे से n steps आगे advance करें, फिर दोनों pointers को एक साथ आगे move करें, ताकि उनके बीच का gap पूरे समय बिल्कुल n nodes चौड़ा रहे।

उदाहरण: Two Pointer Method

#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, nullptr}}}};
    Node* lead = head; Node* trail = head;
    int n = 2;
    for (int i = 0; i < n; i++) lead = lead->next;
    cout << "lead advanced " << n << " steps ahead of trail; gap stays " << n << " nodes wide" << 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 lead = head, trail = head;
        int n = 2;
        for (int i = 0; i < n; i++) lead = lead.next;
        System.out.println("lead advanced " + n + " steps ahead of trail; gap stays " + n + " nodes wide");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1); head.next = Node(2); head.next.next = Node(3)
lead = trail = head
n = 2
for _ in range(n):
    lead = lead.next
print("lead advanced", n, "steps ahead of trail; gap stays", n, "nodes wide")
#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 *lead = head;
    int n = 2;
    for (int i = 0; i < n; i++) lead = lead->next;
    printf("lead advanced %d steps ahead; gap stays %d nodes wide\n", n, n);
    return 0;
}

Remove Node

जब तक leading pointer list के आखिर तक पहुंचता है, trailing pointer target से बिल्कुल एक node पहले positioned है, जो बिल्कुल वह जगह है जहां आपको इसे एक next pointer update करके unlink करने के लिए होना चाहिए।

उदाहरण: Remove Node

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

dummy = Node(0)
dummy.next = Node(1); dummy.next.next = Node(2)
dummy.next.next.next = Node(3); dummy.next.next.next.next = Node(4)
lead = trail = dummy
n = 2
for _ in range(n + 1):
    lead = lead.next
while lead:
    lead = lead.next
    trail = trail.next
trail.next = trail.next.next
c = dummy.next
while c:
    print(c.data, end=" ")
    c = c.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *n4 = malloc(sizeof(struct Node)); n4->data = 4; n4->next = NULL;
    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 *n1 = malloc(sizeof(struct Node)); n1->data = 1; n1->next = n2;
    struct Node dummy = {0, n1};
    struct Node *lead = &dummy, *trail = &dummy;
    int n = 2;
    for (int i = 0; i < n + 1; i++) lead = lead->next;
    while (lead) { lead = lead->next; trail = trail->next; }
    trail->next = trail->next->next;
    for (struct Node *c = dummy.next; c; c = c->next) printf("%d ", c->data);
    return 0;
}

Dummy Node

असली head के ठीक पहले रखा एक dummy node उपयोग करना एक tricky edge case से बचाता है: इसके बिना, list के बिल्कुल पहले node को हटाने को special-case logic चाहिए होती, क्योंकि अन्यथा update करने के लिए कोई previous node नहीं।

उदाहरण: Dummy Node

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* real = new Node{1, new Node{2, nullptr}};
    Node dummy{0, real};
    cout << "dummy.next points at the real head, so removing head needs no special case: " << dummy.next->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 real = new Node(1); real.next = new Node(2);
        Node dummy = new Node(0); dummy.next = real;
        System.out.println("dummy.next points at the real head, so removing head needs no special case: " + dummy.next.data);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

real = Node(1); real.next = Node(2)
dummy = Node(0)
dummy.next = real
print("dummy.next points at the real head, no special case needed:", dummy.next.data)
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *real = malloc(sizeof(struct Node)); real->data = 1; real->next = NULL;
    struct Node dummy = {0, real};
    printf("dummy.next points at real head, no special case needed: %d\n", dummy.next->data);
    return 0;
}

Complexity

यह two-pointer approach target node को एक single O(n) pass में सिर्फ O(1) extra space उपयोग करके हटाता है, एक two-pass solution की तुलना में जो पहले list की length count करता और फिर removal point तक चलता।

उदाहरण: Complexity

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node dummy{0, new Node{1, new Node{2, new Node{3, nullptr}}}};
    Node* lead = &dummy; Node* trail = &dummy;
    int n = 1;
    for (int i = 0; i < n + 1; i++) lead = lead->next;
    while (lead) { lead = lead->next; trail = trail->next; }
    trail->next = trail->next->next;
    cout << "removed in a single O(n) pass, O(1) extra 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 dummy = new Node(0);
        dummy.next = new Node(1); dummy.next.next = new Node(2); dummy.next.next.next = new Node(3);
        Node lead = dummy, trail = dummy;
        int n = 1;
        for (int i = 0; i < n + 1; i++) lead = lead.next;
        while (lead != null) { lead = lead.next; trail = trail.next; }
        trail.next = trail.next.next;
        System.out.println("removed in a single O(n) pass, O(1) extra space");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

dummy = Node(0)
dummy.next = Node(1); dummy.next.next = Node(2); dummy.next.next.next = Node(3)
lead = trail = dummy
n = 1
for _ in range(n + 1):
    lead = lead.next
while lead:
    lead = lead.next
    trail = trail.next
trail.next = trail.next.next
print("removed in a single O(n) pass, O(1) extra 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 *n1 = malloc(sizeof(struct Node)); n1->data = 1; n1->next = n2;
    struct Node dummy = {0, n1};
    struct Node *lead = &dummy, *trail = &dummy;
    int n = 1;
    for (int i = 0; i < n + 1; i++) lead = lead->next;
    while (lead) { lead = lead->next; trail = trail->next; }
    trail->next = trail->next->next;
    printf("removed in a single O(n) pass, O(1) extra space\n");
    return 0;
}
Related Topics

Linked List का Middle ढूँढना · दो Sorted Lists को Merge करना · Floyd का Cycle Detection Algorithm · Linked List को Reverse करना

{# 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. Lead pointer को n steps move करना लेकिन यह न जांचना कि list में कम से कम n nodes हैं, इसलिए यह आखिर से आगे निकल जाता है।
  2. Trailing pointer को हटाने वाले node पर रोकना बजाय इससे पहले वाले node पर, इसलिए आप next relink नहीं कर सकते।
  3. एक dummy node उपयोग न करना, इसलिए head हटाना (जब n length के बराबर हो) fail होता है।
चैप्टर सारांश
  • Linked lists nodes को pointers के ज़रिए connect करते हैं, singly, doubly, और circular forms में।
  • आम operations में reversal, बीच ढूंढना, sorted lists merge करना, और आखिर से nth node हटाना शामिल है।
  • Floyd का cycle detection किसी list में loops ढूंढता है।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Find Middle of Linked List Next Lesson → Stack Introduction

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.