टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: सीटीसीआई शैली समस्या २.३: सिंगली लिंक्ड लिस्ट के बीच का नोड सिर्फ उसी नोड के पॉइंटर से मिटाएँ। अगला मान कॉपी करो, अगला छोड़ो, और समझो आखिरी नोड क्यों फेल होता है।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
आप एक कोंगा लाइन में हैं। कोई कंधे पर थपथपाकर कहता है: खुद को निकालो। पीछे वाले तक पहुँच नहीं सकते, इसलिए उनसे नहीं कह सकते कि वे आपको छोड़ दें। जो चाल चलती है वह अजीब है: आप आगे वाले बन जाते हैं। उनका पोशाक, उनका नाम-टैग कॉपी करो, फिर उन्हें लाइन से बाहर निकालो और खाली जगह बंद करो। बाकी चेन अभी भी पूरी लगती है। सिंगली लिंक्ड लिस्ट पर मिडिल नोड मिटाना यही है।
यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू के क्लासिक लिंक्ड-लिस्ट ट्रिक जैसी समस्या, किसी किताब की नकल नहीं। सीटीसीआई जावा श्रृंखला का हिस्सा।
१. रोज़मर्रा की उपमा
सिंगली लिंक्ड लिस्ट एकतरफा कोंगा लाइन है। हर व्यक्ति सिर्फ अगले को जानता है। आपको लाइन का हेड नहीं मिलता। सिर्फ बीच के किसी व्यक्ति का पॉइंटर मिलता है, और काम है: उसे निकालना।
सामान्य अनलिंक के लिए पिछला नोड चाहिए:
prev.next = node.next
यहाँ prev नहीं है। इसलिए चाल:
१. अगले की पहचान चुरा लो (next.data को मौजूदा नोड में कॉपी करो)।
२. अगले को छोड़ दो (current.next = next.next)।
बीच वाला “स्लॉट” ऑब्जेक्ट के रूप में रहता है, लेकिन अब उसमें अगला मान है और वह वहाँ पॉइंट करता है जहाँ अगला करता था। बाहर से देखने पर वह मान सीक्वेंस से गायब है।
२. सादे शब्दों में समस्या
इनपुट: एक Node रेफरेंस node जो सिंगली लिंक्ड लिस्ट का पहला या आखिरी नोड नहीं है। हेड नहीं मिलता।
आउटपुट: लिस्ट म्यूटेट करो ताकि node पर जो मान था वह सीक्वेंस में न दिखे। ऐसा लगे जैसे बीच का नोड मिट गया।
नोड का आकार:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
उदाहरण:
| पहले | यह मिटाओ | बाद में | क्यों |
|---|---|---|---|
a → b → c → d → e |
c वाला नोड |
a → b → d → e |
c बन जाता है d, फिर पुराना d छोड़ दिया जाता है |
1 → 2 → 3 → 4 |
2 वाला नोड |
1 → 3 → 4 |
2 के स्लॉट में 3 कॉपी, पुराना 3 छोड़ो |
1 → 2 → 3 → 4 |
3 वाला नोड |
1 → 2 → 4 |
वही आइडिया एक कदम आगे |
कोड से पहले साफ़ करो (ज़ोर से बोलो):
- क्या नोड आखिरी नहीं होने की गारंटी है? (क्लासिक: हाँ, या “आखिरी को छोड़ कोई भी”।)
- क्या हेड नहीं होने की गारंटी है? (अक्सर हाँ; हेड मिटाने का अलग कॉन्ट्रैक्ट।)
- क्या
dataओवरराइट कर सकते हैं? (हाँ। पूरी चाल यही है।) - सिंगली या डबली? (यहाँ: सिंगली।)
- सिर्फ एक नोड वाली लिस्ट? (स्कोप से बाहर; कॉपी करने को अगला नहीं।)
इस लेख में: बीच जैसा नोड जिसका next नॉन-नल है, पूर्णांक, इन-प्लेस म्यूटेट, सफलता या वॉइड लौटाओ।
३. पहले सोचो
जो नहीं कर सकते
- हेड से चलकर
prevढूँढना। हेड ही नहीं है। node = node.nextकरना। यह सिर्फ लोकल वेरिएबल बदलता है। पिछले नोड काnextअभी भी पुराने ऑब्जेक्ट पर है।- बिना रीवायर किए नोड फ्री करना। चेन में वह अभी भी है।
एकमात्र व्यावहारिक चाल
अगर node.next मौजूद है:
node.data = node.next.data
node.next = node.next.next
आप अगले नोड को भौतिक रूप से हटाते हो, उसके पेलोड को मौजूदा में कॉपी करने के बाद। असर: node पर जो मान था वह चला गया। आगे के मान एक “लॉजिकल” स्लॉट बाएँ सरकते हैं।
आखिरी नोड क्यों फेल
अगर node.next == null, तो चुराने को पहचान नहीं, छोड़ने को अगला नहीं। पिछले पॉइंटर (या सेंटिनल डिज़ाइन) के बिना आखिरी मान नहीं हटा सकते। इंटरव्यू में साफ़ कहो: यह अल्गोरिदम असली आखिरी नोड नहीं मिटाता।
कुछ इंटरव्यूअर “डमी मार्क / थ्रो / false लौटाओ” मान लेते हैं। साफ़ कॉन्ट्रैक्ट चुनो और उसी पर रहो।
४. जावा समाधान
/**
* Deletes a middle node from a singly linked list given only that node.
* Copies the next node's data into this node, then skips the next node.
* Does not work for the last node (no next to copy from).
*
* @return true if deleted, false if node is null or is the last node
*/
boolean deleteMiddleNode(Node node) {
if (node == null || node.next == null) {
// Cannot delete last node (or a null reference) this way.
return false;
}
Node next = node.next;
node.data = next.data;
node.next = next.next;
return true;
}
a → b → c → d → e पर वॉकथ्रू, c वाला नोड मिटाएँ:
| कदम | node.data |
node.next किधर |
हेड से लिस्ट |
|---|---|---|---|
| शुरू | c |
d |
a → b → c → d → e |
| डेटा कॉपी | d |
d (वही ऑब्जेक्ट) |
a → b → d → d → e (क्षण भर दो नोड्स पर d) |
| अगला छोड़ो | d |
e |
a → b → d → e |
पुराना d नोड अनलिंक हो जाता है और जीसी के लिए तैयार। जिसने अभी भी पुराने c ऑब्जेक्ट का पॉइंटर रखा है, वह अब उस ऑब्जेक्ट में d देखता है। आम ट्रेडऑफ़: नोड ऑब्जेक्ट की पहचान और सीक्वेंस में मान की पहचान एक नहीं।
मानसिक टेस्ट के लिए छोटा ड्राइवर:
Node build(int... vals) {
Node dummy = new Node(0);
Node t = dummy;
for (int v : vals) {
t.next = new Node(v);
t = t.next;
}
return dummy.next;
}
// head: 1 → 2 → 3 → 4 → 5
// delete the node with value 3 (must look it up only for the demo)
Node head = build(1, 2, 3, 4, 5);
Node target = head.next.next; // the 3
deleteMiddleNode(target);
// list is now 1 → 2 → 4 → 5
असली कॉल साइट पर इंटरव्यूअर सीधे target देता है। हेड से कभी खोज नहीं करते।
५. जटिलता तालिका
| तरीका | समय | अतिरिक्त जगह | नोट |
|---|---|---|---|
| अगला कॉपी + छोड़ो | ओ(१) | ओ(१) | सिर्फ कॉन्स्टेंट पॉइंटर काम |
हेड से चलकर prev ढूँढो |
ओ(एन) | ओ(१) | हेड चाहिए; प्रॉम्प्ट मना करता है |
| बिना उस मान के पूरी लिस्ट कॉपी | ओ(एन) | ओ(एन) | ज़रूरत से ज़्यादा, फिर भी हेड चाहिए |
जब बाधाएँ लागू हों, यह उन दुर्लभ लिंक्ड-लिस्ट समस्याओं में है जो सच में ओ(१) समय में होती हैं।
६. किनारे के केस और आम गलतियाँ
इंटरव्यूअर ये छूते हैं:
- आखिरी नोड →
falseलौटाओ, थ्रो करो, या “सपोर्ट नहीं” लिखो।node.next.dataपर एनपीई मत दो। - नल नोड → पहले गार्ड।
- दो नोड की लिस्ट, दोनों में से पहला मिटाओ → चलता है: पहला दूसरा बन जाता है, फिर दूसरा छूटता है। लिस्ट एक नोड रह जाती है। “दो में से पहला” मिडिल गिना जाए या नहीं, वर्डिंग पर निर्भर; अल्गो फिर भी चलता है।
- लंबाई > २ पर हेड → तकनीकी रूप से अल्गो “चलता” है (हेड का डेटा ओवरराइट, पुराना दूसरा छोड़ो)। कई समस्याएँ फिर भी कहती हैं “पहला या आखिरी नहीं”। कही गई बाधा मानो।
- डुप्लिकेट मान → ठीक। उस पोज़िशन की एक घटना हटती है, “सभी बराबर” नहीं।
- मिटे मान के पुराने नोड के बाहरी रेफरेंस → अब उस ऑब्जेक्ट पर हैं जिसमें अगला मान है। शेयर्ड लिस्ट हो तो यह बोलो।
आम गलतियाँ:
१. सिर्फ node = node.next। लोकल रीबाइंड कुछ अनलिंक नहीं करता।
२. डेटा कॉपी भूलना। बिना कॉपी अगला छोड़ने से बीच का मान रह जाता है और अगला जाता है: मिडिल मिटाने का उल्टा।
३. मानना कि आखिरी नोड फ्री कर सकते हो। सिर्फ उस पॉइंटर से सिंगली लिस्ट पर नहीं।
४. वॉइड लौटाकर फेल नज़रअंदाज़। आखिरी-नोड केस के लिए बूलियन या साफ़ एक्सेप्शन बेहतर।
५. सोचना कि नोड ऑब्जेक्ट गायब हो गया। node वाला ऑब्जेक्ट रहता है; उसका पेलोड बदलता है। “मिटाना” सीक्वेंस के लिए लॉजिकल है, उस जावा ऑब्जेक्ट के लिए हमेशा भौतिक नहीं।
७. दोस्त को समझाने वाला सार
मिडिल नोड मिटाना पूछता है: सिंगली लिंक्ड लिस्ट से एक मान हटाओ जब सिर्फ वही नोड हो, हेड नहीं।
१. पिछले पॉइंटर को रीवायर नहीं कर सकते। वह है ही नहीं। २. अगले नोड का डेटा मौजूदा में कॉपी करो। ३. मौजूदा को अगले के पार पॉइंट करो। ४. आखिरी नोड का अगला नहीं, इसलिए चाल फेल। शुरू में ही कहो।
तीन पंक्ति का बॉडी लिख सको और तीस सेकंड में आखिरी-नोड सीमा समझा सको, तो समस्या २.३ तुम्हारी है।
श्रृंखला
- गाइड: सीटीसीआई श्रृंखला गाइड
- पिछला: के-वाँ अंतिम लौटाओ
- अगला: पार्टीशन