सम लिस्ट: लिंक्ड लिस्ट में रखी संख्याओं का जोड़ (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: सीटीसीआई-शैली समस्या २.५: दो संख्याएँ लिंक्ड लिस्ट में, हर नोड में एक अंक, इकाई का अंक सिर पर। दोनों पर कैरी के साथ चलो और योग लिस्ट बनाओ। आगे-क्रम वाले फॉलो-अप की छोटी नोट।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

स्कूल वाली कागज़ी जोड़: दो बड़ी संख्याएँ दाईं तरफ संरेखित करो, इकाई से शुरू करो, एक अंक लिखो, बाईं ओर कैरी भेजो। अंक स्तंभों में रहते हैं। कैरी स्तंभों के बीच थोड़ी याददाश्त है।

अब हर अंक को सिंगली लिंक्ड लिस्ट के एक नोड में रखो, और इकाई का अंक सिर पर रखो। लिस्ट पर चलना ठीक वैसा ही है जैसे कागज़ पर दाएँ से बाएँ स्तंभ चलना। यही सम लिस्ट है।

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

रोज़मर्रा का उदाहरण

दो रसीदें, हर संख्या चिपचिपे नोटों पर अंक-दर-अंक:

7 → 1 → 6 मतलब ६१७ (७ इकाई, १ दहाई, ६ सैकड़ा)।
5 → 9 → 2 मतलब २९५।

कागज़ की तरह जोड़ो:

स्तंभ	अंक	योग + कैरी इन	लिखो	कैरी आउट
इकाई	७ + ५	१२	२	१
दहाई	१ + ९	११	१	१
सैकड़ा	६ + २	९	९	०

कागज़ पर परिणाम: ९१२। उल्टी लिस्ट में: 2 → 1 → 9।

लिस्ट पहले से जोड़ के क्रम में अंक रखती है। पहले पलटने की ज़रूरत नहीं। बस चलो और कैरी ले जाओ।

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

इनपुट: दो सिंगली लिंक्ड लिस्ट के सिर। हर नोड में एक अंक 0-9। अंक उल्टे क्रम में: सिर इकाई का स्थान है।

आउटपुट: योग दर्शाने वाली नई लिस्ट का सिर, भी उल्टे क्रम में (इकाई सिर पर)।

नोड का आकार:

class Node {
    int data;
    Node next;

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

उदाहरण:

लिस्ट ए	लिस्ट बी	संख्याएँ	योग लिस्ट	क्यों
`7 → 1 → 6`	`5 → 9 → 2`	६१७ + २९५	`2 → 1 → 9`	९१२
`9 → 9`	`1`	९९ + १	`0 → 0 → 1`	१००; अंतिम कैरी नया नोड बनता है
`1 → 2`	`3 → 4 → 5`	२१ + ५४३	`4 → 6 → 5`	अलग लंबाई; ५६४
`0`	`0`	० + ०	`0`	फिर भी एक अंक
`null`	`5 → 1`	खाली = ०	`5 → 1`	एक तरफ़ खाली

कोड से पहले साफ़ करो (ज़ोर से बोलो):

उल्टा क्रम (इकाई सिर पर) मुख्य समस्या है। आगे क्रम फॉलो-अप है।
सिर्फ़ अंक, या पूरे पूर्णांक? हर नोड में अंक 0-9।
कोई लिस्ट खाली या null हो सकती है?
नए नोड, या इनपुट बदलना? नए नोड बेहतर, इनपुट नष्ट न हों।
वैचारिक संख्या में आगे शून्य? अक्सर इनपुट साफ़; फिर भी बचा कैरी संभालो।

कोड से पहले कैसे सोचें

पहले यह मत करो

हर लिस्ट को int या long में बदलकर जोड़ना और फिर बनाना। ६४ बिट से लंबी संख्याओं पर टूट जाता है, और अंक-लिस्ट का आधा मतलब यही है। इंटरव्यूअर नोटिस करते हैं।

उल्टा क्रम: कागज़ी जोड़ से मिलाओ

तीन चीज़ें रखो:

१. लिस्ट ए पर पॉइंटर। २. लिस्ट बी पर पॉइंटर। ३. पूर्णांक carry (आधार १० में ० या १; अंक ०-९ हों तो आमतौर पर ० या १)।

हर कदम:

sum = carry
if A not null: sum += A.data; A = A.next
if B not null: sum += B.data; B = B.next
digit = sum % 10
carry = sum / 10
append a new node with digit

लूप तब तक जब तक किसी लिस्ट में नोड बाकी हों या कैरी शून्य न हो। आखिरी शर्त ही 99 + 1 में तीसरा अंक बनाती है।

डमी सिर लगाओ ताकि पहला असली अंक हमेशा dummy.next हो। पहले अपेंड के लिए अलग केस नहीं।

रिकर्सिव संस्करण (वही विचार)

आधार: दोनों null और कैरी ० → null लौटाओ। वरना मौजूदा सिरों (या null हो तो ०) और कैरी से योग निकालो, sum % 10 वाला नोड बनाओ, next को पूंछों पर नए कैरी वाली रिकर्सिव कॉल से जोड़ो। वही जटिलता, स्टैक गहराई O(अधिकतम लंबाई)।

जावा इंटरव्यू में डमी सिर वाला इटरेटिव अक्सर साफ़ लगता है। कैरी सही हो तो दोनों ठीक।

फॉलो-अप विचार: आगे क्रम (इकाई पूंछ पर)

अब सिर सबसे महत्वपूर्ण अंक हैं। कागज़ी जोड़ सबसे पहले कम महत्वपूर्ण चाहती है, तो क्रम विरोध करता है।

छोटा प्लान (यहाँ पूरा प्रोडक्शन कोड ज़रूरी नहीं):

१. दोनों लिस्ट की लंबाई निकालो। २. छोटी लिस्ट को आगे शून्य से पैड करो (नए नोड, या रिकर्शन में वैचारिक पैड) ताकि लंबाई बराबर हो। ३. अंत तक रिकर्स करो, लौटते समय जोड़ो, आंशिक लिस्ट और कैरी लौटाओ (रैपर ऑब्जेक्ट या छोटी रिजल्ट क्लास)। ४. अंतिम कैरी बचे तो नए सिर अंक को आगे जोड़ो।

दोनों इनपुट पलटो, उल्टे-क्रम वाला हल चलाओ, परिणाम पलटो। काम करता है और समझाना आसान है। बिना क्रम बदले जोड़ दिखाने के लिए पैड-एंड-रिकर्स भी माँगा जा सकता है।

इस लेख का मुख्य फोकस उल्टा क्रम ही रहता है।

जावा हल (उल्टा क्रम, इटरेटिव)

/**
 * Adds two numbers stored as reverse-order digit lists.
 * Example: 7→1→6 + 5→9→2 represents 617 + 295 → 2→1→9 (912).
 */
Node sumLists(Node l1, Node l2) {
    Node dummy = new Node(0);
    Node tail = dummy;
    int carry = 0;

    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) {
            sum += l1.data;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.data;
            l2 = l2.next;
        }

        tail.next = new Node(sum % 10);
        tail = tail.next;
        carry = sum / 10;
    }

    return dummy.next;
}

7 → 1 → 6 और 5 → 9 → 2 का वॉकथ्रू:

कदम	l१ अंक	l२ अंक	कैरी इन	योग	लिखो	कैरी आउट	अब तक परिणाम
१	७	५	०	१२	२	१	`2`
२	१	९	१	११	१	१	`2 → 1`
३	६	२	१	९	९	०	`2 → 1 → 9`
४	-	-	०	रुक			हो गया

रिकर्सिव स्केच (वही उल्टा-क्रम करार):

Node sumListsRecursive(Node l1, Node l2, int carry) {
    if (l1 == null && l2 == null && carry == 0) {
        return null;
    }

    int sum = carry;
    if (l1 != null) {
        sum += l1.data;
    }
    if (l2 != null) {
        sum += l2.data;
    }

    Node result = new Node(sum % 10);
    Node next1 = (l1 == null) ? null : l1.next;
    Node next2 = (l2 == null) ? null : l2.next;
    result.next = sumListsRecursive(next1, next2, sum / 10);
    return result;
}

// Public entry: sumListsRecursive(a, b, 0)

आगे क्रम एक छोटी झलक

अगर अंक सबसे महत्वपूर्ण से कम महत्वपूर्ण (6 → 1 → 7 मतलब ६१७):

विकल्प अ: दोनों पलटो, sumLists, जवाब पलटो।
विकल्प ब: छोटी पैड करो, पूंछ तक रिकर्स, लौटते जोड़ो, कैरी + नोड छोटी हेल्पर क्लास में लपेटो, बचा कैरी आगे लगाओ।

विकल्प अ ऊपर वाला कोड दोबारा इस्तेमाल करता है। विकल्प ब क्लासिक “बिना पलटे” फॉलो-अप है। इंटरव्यू में एक नाम बताना काफ़ी है, फिर उल्टा क्रम साफ़ लिखो।

जटिलता

	लागत	क्यों
समय	O(m, n में बड़ा)	दोनों लिस्ट पर एक पास; अंतिम कैरी के लिए ज़्यादा से ज़्यादा एक अतिरिक्त नोड
अतिरिक्त जगह (इटरेटिव)	आउटपुट के लिए O(m, n में बड़ा)	आउटपुट आकार योग की लंबाई; सहायक पॉइंटर O(१)
अतिरिक्त जगह (रिकर्सिव)	O(m, n में बड़ा) स्टैक + आउटपुट	गहराई लंबी लिस्ट के साथ

इनपुट लंबाई में रैखिक से बेहतर नहीं: हर अंक योग को छू सकता है।

किनारे के केस जो इंटरव्यूअर छूते हैं

१. अलग लंबाई। 1 → 2 और 3 → 4 → 5। कोई भी पॉइंटर null न हो तब तक लूप। गायब तरफ़ ० जोड़ती है। २. अंतिम कैरी। 9 → 9 + 1 → 0 → 0 → 1। लूप शर्त में carry != 0 ज़रूरी। ३. एक लिस्ट null या खाली। योग दूसरी की कॉपी (प्लस कैरी श्रृंखला)। null पर क्रैश न हो। ४. दोनों एक नोड। 5 + 7 → 2 → 1 जब कैरी हो। ५. शून्य। 0 + 0 → 0। शून्य के लिए null लौटाना आमतौर पर गलत, जब तक समस्या न कहे खाली मतलब शून्य। ६. सब नौ। लंबी कैरी श्रृंखला; फिर भी प्रति अंक एक नया नोड, ज़्यादा से ज़्यादा एक अतिरिक्त। ७. गलती से इनपुट बदलना। new Node(...) से बनाना कॉलर की लिस्ट बचाता है। ८. आगे-क्रम जाल। बीच में अंक क्रम पलट दें तो कोड से पहले ज़ोर से क्रम दोहराओ।

आम गलतियाँ:

दोनों लिस्ट खत्म होने पर रुक जाना जबकि कैरी अभी १ है।
कैरी के लिए sum % 10 और अंक के लिए sum / 10 (उल्टा)।
int में बदलकर ओवरफ़्लो।
डमी सिर भूलना और पहले नोड को अलग केस बनाकर कोड गंदा करना।

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

सम लिस्ट कागज़ी जोड़ है जहाँ हर अंक लिंक्ड-लिस्ट नोड है और इकाई का स्थान सिर पर है।

१. दोनों लिस्ट साथ कैरी लेकर चलो। २. हर कदम: दो अंक (या लिस्ट खत्म हो तो शून्य) प्लस कैरी जोड़ो, sum % 10 लिखो, कैरी sum / 10 करो। ३. तब तक चलो जब तक दोनों लिस्ट खत्म और कैरी शून्य। ४. डमी सिर से अपेंड आसान रहता है। ५. आगे क्रम वही गणित है, पलटने के बाद, या पैड करके ऊपर से रिकर्स के बाद।

अगर बोर्ड पर 7→1→6 और 5→9→2 बिना अंतिम कैरी पर अटकें जोड़ सको, समस्या २.५ तुम्हारी है।