डुप्लिकेट हटाओ: बिना क्रम वाली लिंक्ड लिस्ट से दोहराव मिटाएँ (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली समस्या २.१: सिंगली लिंक्ड लिस्ट से डुप्लिकेट मान हटाएँ। हैशसेट से ओ(एन) चलान, फिर बिना बफ़र रनर पॉइंटर से ओ(एन²)।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम्हारे फ़ोन की कॉन्टैक्ट सूची में “आना” तीन बार है, “सैम” दो बार, और कुछ नाम साफ़ हैं। हर व्यक्ति एक बार चाहिए। वर्णक्रम की परवाह नहीं। सूची पर चलो, जिन्हें रखा याद रखो, बाकी काट दो। लिंक्ड लिस्ट पर “डुप्लिकेट हटाओ” यही है।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू के क्लासिक लिंक्ड-लिस्ट वार्मअप जैसी समस्या, किसी किताब की नकल नहीं। सीटीसीआई जावा श्रृंखला का हिस्सा। अध्याय २ यहीं से शुरू होता है।

---

१. रोज़मर्रा की उपमा

एक डोरी पर चिपचिपे नोट सोचो। हर नोट पर एक संख्या। नोट सिर्फ अगले नोट की ओर इशारा कर सकते हैं (सिंगली लिंक्ड लिस्ट)।

• पहले नोट से चलना शुरू करो।
• अगर वह संख्या नई है, नोट रखो और संख्या याद रखो।
• अगर वह संख्या पहले आ चुकी है, नोट काट दो और डोरी जोड़ दो।

सॉर्ट नहीं कर रहे। गिनती नहीं गिन रहे। हर मान की पहली उपस्थिति रखो, बाद की प्रतियाँ फेंको।

---

२. सादे शब्दों में समस्या

इनपुट: पूर्णांकों की बिना क्रम सिंगली लिंक्ड लिस्ट का हेड (या null)।

आउटपुट: वही संरचना, बिना डुप्लिकेट मानों के। पहली उपस्थितियों का क्रम वैसा ही। अक्सर इन-प्लेस बदलते हैं और void लौटाते हैं (या वही हेड)।

जो नोड रूप हम लेते हैं:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

उदाहरण:

पहले (हेड → …)	बाद	क्यों
1 → 2 → 3 → 2 → 1	1 → 2 → 3	दूसरा 2 और दूसरा 1 हटे
5 → 5 → 5	5	सिर्फ पहला बचा
7	7	एक नोड, हटाने को कुछ नहीं
null	null	खाली सूची
1 → 2 → 3	1 → 2 → 3	पहले से यूनिक

कोड से पहले पूछो (इंटरव्यू में ज़ोर से बोलो):

• सिंगली या डबल लिंक्ड? (यहाँ: सिंगली।)
• अतिरिक्त मेमोरी चलेगी? (मुख्य हल हाँ; फॉलो-अप नहीं।)
• पहली उपस्थिति स्थिर रखें, या मनचाहा पुनर्क्रम?
• ऋणात्मक और शून्य? (किसी भी int की तरह।)
• नई सूची बनाएँ या मौजूदा नोड संपादित करें?

इस लेख में: इन-प्लेस बदलना, पहली उपस्थिति रखना, पूर्णांक, सिंगली लिंक्ड।

---

३. पहले सोचो (ब्रूट, हैश, फिर बिना बफ़र)

ब्रूट सहज ज्ञान

हर नोड के लिए सूची का बाकी हिस्सा देखो और वही मान वाले बाद के नोड हटा दो। यह फॉलो-अप के करीब है। घोंसलेदार लूप: समय ओ(एन²), अतिरिक्त जगह ओ(१)।

मुख्य विचार: जो रखा, याद रखो

HashSet<Integer> में वे मान रखो जिन्हें पहले ही रखा। एक पॉइंटर सूची पर चलता है। दूसरा (या “पिछला” रेफ़रेंस) एक कदम पीछे रहता है ताकि नोड काट सको।

• मान पहली बार: सेट में डालो, previous आगे बढ़ाओ।
• मान पहले से सेट में: previous.next = current.next से वर्तमान नोड छोड़ दो।

एक ही पास। हैश खोज औसत ओ(१)। कुल समय ओ(एन), अतिरिक्त जगह सबसे खराब ओ(एन) (सभी मान अलग)।

फॉलो-अप: बफ़र मना

इंटरव्यूअर सेट मना कर देता है। हर नोड current के लिए दूसरा पॉइंटर runner current से बाकी सूची पर चलाओ। जब runner.next का डेटा current जैसा हो, runner.next काट दो। वरना runner आगे।

बाहरी × भीतरी लूप: समय ओ(एन²), अतिरिक्त जगह ओ(१)। सही, बस धीमा। जब मेमोरी तंग हो या सेट वर्जित हो, अच्छा जवाब।

---

४. जावा हल

(क) हैशसेट, एक पास

import java.util.HashSet;
import java.util.Set;

/**
 * Removes duplicate values from an unsorted singly linked list.
 * Keeps the first occurrence of each value. Mutates the list in place.
 */
void removeDups(Node head) {
    if (head == null) {
        return;
    }

    Set<Integer> seen = new HashSet<>();
    Node previous = null;
    Node current = head;

    while (current != null) {
        if (seen.contains(current.data)) {
            // Drop current: bridge previous over it.
            previous.next = current.next;
        } else {
            seen.add(current.data);
            previous = current;
        }
        current = current.next;
    }
}

1 → 2 → 3 → 2 → 1 का चलान:

current.data	पहले seen	क्रिया	कदम के बाद सूची
1	{}	१ जोड़ो, रखो	1 → 2 → 3 → 2 → 1
2	{1}	२ जोड़ो, रखो	वही
3	{1,2}	३ जोड़ो, रखो	वही
2	{1,2,3}	पहले देखा, अनलिंक	1 → 2 → 3 → 1
1	{1,2,3}	पहले देखा, अनलिंक	1 → 2 → 3

(ख) रनर पॉइंटर, बिना अतिरिक्त बफ़र

/**
 * Same goal as removeDups, but no HashSet and no extra O(N) memory.
 * For each node, scan the rest of the list and remove matching values.
 */
void removeDupsNoBuffer(Node head) {
    Node current = head;

    while (current != null) {
        Node runner = current;
        while (runner.next != null) {
            if (runner.next.data == current.data) {
                // Skip the duplicate node.
                runner.next = runner.next.next;
            } else {
                runner = runner.next;
            }
        }
        current = current.next;
    }
}

runner head से नहीं, current से क्यों शुरू: सिर्फ current.data की बाद वाली प्रतियाँ साफ़ करनी हैं। पहले वाले नोड अपने मानों के हिसाब से साफ़ हो चुके। current से शुरू भीतरी स्कैन छोटा रखता है और उपसर्ग को दोबारा नहीं छूता।

---

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह	नोट
हैशसेट चलान	औसत ओ(एन)	ओ(एन)	एन = नोड; जगह अलग मान रखती है
रनर (बिना बफ़र)	ओ(एन²)	ओ(१)	सूची के घोंसलेदार स्कैन
ऐरे में कॉपी, यूनिक, फिर बनाओ	ओ(एन)	ओ(एन)	काम करता है, पर अक्सर “लिंक्ड लिस्ट कौशल” नहीं माँगते

उत्पादन और ज़्यादातर इंटरव्यू में हैशसेट चुनो, जब तक अतिरिक्त मेमोरी मना न हो। जब “स्थिर जगह” या “बिना बफ़र” कहें, रनर लगाओ।

---

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

• खाली सूची (null हेड) → तुरंत लौटो। कुछ मत छुओ।
• एक नोड → वैसा ही छोड़ो।
• सभी मान समान → सिर्फ हेड बचे।
• अंत में डुप्लिकेट → previous आखिरी नोड भी काट सके।
• कोई डुप्लिकेट नहीं → सेट एन तक बढ़े; संरचना वैसी।
• ऋणात्मक और शून्य → हैश और == धनात्मक की तरह ही।
• बहुत लंबी सूची → हैशसेट रैखिक रहता है; रनर सच में धीमा। यह ट्रेडऑफ़ ज़ोर से बोलो।

आम गलतियाँ:

१. अनलिंक करते समय previous भूलना। सिर्फ current बढ़ाने से previous.next नहीं जुड़ता, डुप्लिकेट सूची में रहता है। २. मिटाने पर भी previous बढ़ाना। मिटाने के बाद previous आखिरी रखे नोड पर रहता है। previous तभी हिलाओ जब current रखा हो। ३. हेड खो देना। इस समस्या में पहला नोड हमेशा रहता है (खुद का “बाद वाला” डुप्लिकेट नहीं बन सकता)। दूसरी नियमों वाली समस्या में डमी हेड या लौटाया हेड चाहिए। ४. हर बार बेपरवाही से runner को head से शुरू। हो सकता है, पर काम दोहरा और किनारे उलझे। current से साफ़। ५. बाद में ऑब्जेक्ट पेलोड पर ==। यहाँ data int है, इसलिए == सही। Integer या कस्टम टाइप पर equals और hashCode सोचो।

नल-सुरक्षित न्यूनतम प्रवेश:

void removeDupsSafe(Node head) {
    // null head is a no-op inside removeDups
    removeDups(head);
}

---

७. दोस्त को समझाने वाला सार

“डुप्लिकेट हटाओ” पूछता है: सिंगली लिंक्ड लिस्ट में हर मान एक बार; पहली जीत।

१. हैशसेट रास्ता: एक चलान, रखे मान याद, दोहराव काटो। समय ओ(एन), जगह ओ(एन)। २. बिना बफ़र: हर नोड के लिए रनर से बाकी स्कैन, मिलते नोड काटो। समय ओ(एन²), जगह ओ(१)। ३. मिटाते समय हमेशा next जोड़ो। “रखा” पॉइंटर मिटे नोड के पार मत बढ़ाओ। ४. खाली और एक-नोड सूची आसान जीत। सब-समान सूची एक नोड रह जाती है।

तीस सेकंड में यह कह सको और दोनों संस्करण बिना अटक लिख सको, तो समस्या २.१ तुम्हारी है।

---

श्रृंखला

• गाइड: सीटीसीआई श्रृंखला गाइड
• पिछला: स्ट्रिंग रोटेशन
• अगला: अंत से के-वाँ लौटाओ