सीटीसीआई २.४ पार्टीशन: लिंक की गई सूची को x के आसपास बाँटना

टीएल;डीआर

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

हवाई अड्डे की सुरक्षा में दो लाइनें हैं। एक वजन सीमा से हल्के बैग के लिए, एक सीमा पर या उससे भारी बैग के लिए। लोग बेतरतीब क्रम में आते हैं। आप वजन से पूरा सॉर्ट नहीं करते। बस इतना चाहिए कि हर हल्का बैग बाईं लाइन में और हर भारी बैग दाईं लाइन में पहुँचे। लिंक की गई सूची के लिए यही पार्टीशन है: मान x के आसपास एक काट, पूरा सॉर्ट नहीं।

यह पोस्ट सीटीसीआई जावा सीरीज़ की समस्या २.४ है, अध्याय २ (लिंक्ड लिस्ट)। मूल समझाई और कोड, किताब की नकल नहीं।

---

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

आपको पूर्णांकों की एक तरफ़ा लिंक की गई सूची का हेड मिलता है, और एक पूर्णांक x।

लक्ष्य: नोडों को इस तरह फिर से लगाओ कि जिनकी वैल्यू x से सख्ती से छोटी है, वे उन नोडों से पहले आएँ जिनकी वैल्यू x से बड़ी या बराबर है।

इंटरव्यू में मायने रखने वाली बातें:

• x के बराबर नोड दाईं तरफ रहते हैं ("बड़ा या बराबर" समूह के साथ)। अलग मध्य बाल्टी ज़रूरी नहीं, जब तक आप खुद न बनाएँ।
• स्थिर क्रम (हर तरफ मूल सापेक्ष क्रम रखना) अच्छा लगता है और दो-सूची तरीके से अक्सर मुफ़्त मिल जाता है। समस्या हमेशा स्थिरता नहीं माँगती।
• मौजूदा नोड दोबारा इस्तेमाल करें। हर वैल्यू के लिए नया नोड न बनाएँ, जब तक साक्षात्कारकर्ता न कहे।

क्लासिक उदाहरण:

इनपुट:  3 → 5 → 8 → 5 → 10 → 2 → 1 ,  x = 5
एक मान्य आउटपुट:  3 → 1 → 2 → 10 → 5 → 5 → 8

काट के बाएँ: 3, 1, 2 (सब < 5)। दाएँ: 10, 5, 5, 8 (सब >= 5)। कोई और मान्य सूची हर आधे के अंदर क्रम बदल सकती है, जब तक काट का नियम सही रहे।

---

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

गलत आदत: पूरी सूची सॉर्ट करना

पूरा सॉर्ट काट का नियम पूरा करता है, लेकिन माँगे से ज़्यादा काम है। पार्टीशन, सॉर्ट से कमज़ोर है। लक्ष्य रैखिक समय और कुछ अतिरिक्त पॉइंटर।

मुख्य विचार: दो सूचियाँ, फिर जोड़

सूची एक बार घूमो। हर नोड पर अलग करो (node.next = null, असली अगला सेव करने के बाद), फिर दो चेन में से एक में जोड़ो:

१. बिफोर सूची: वैल्यू < x २. आफ्टर सूची: वैल्यू >= x

हर चेन के लिए हेड और टेल रखो ताकि जोड़ना O(1) हो। घूमने के बाद:

• अगर बिफोर खाली है, आफ्टर का हेड लौटाओ।
• वरना beforeTail.next = afterHead करो और बिफोर का हेड लौटाओ।
• afterTail.next = null रखो (या रास्ते में ही तोड़ो) ताकि पुराने लिंक से चक्र न बने।

पूरा एल्गोरिदम यही है। एक पास। चार पॉइंटर (या दो डमी हेड)। व्हाइटबोर्ड पर समझाना आसान।

वैकल्पिक तरीका: हेड और टेल से बढ़ाना

एक और शैली एक ही नतीजा सूची को दोनों सिरों से बढ़ाती है:

• वैल्यू < x आगे डाली जाती हैं (नया हेड)।
• वैल्यू >= x पीछे जोड़ी जाती हैं।

यह भी एक पास में पार्टीशन करता है। बाएँ तरफ क्रम अक्सर मूल के मुकाबले उल्टा हो जाता है, जो तब ठीक है जब स्थिरता न माँगी हो। जब स्थिर क्रम और "बायाँ डिब्बा, दायाँ डिब्बा" वाली कहानी चाहिए, दो-सूची मर्ज साफ़ रहता है।

---

जावा समाधान (दो-सूची मर्ज)

/** Singly linked list node used across Chapter 2 examples. */
public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

/**
 * Partition list around x: all nodes with val < x before nodes with val >= x.
 * Stable within each side if you always append to that side's tail.
 * Reuses existing nodes. Returns the new head.
 */
public static ListNode partition(ListNode head, int x) {
    ListNode beforeHead = null;
    ListNode beforeTail = null;
    ListNode afterHead = null;
    ListNode afterTail = null;

    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        // Detach so old links cannot form a cycle after the merge.
        current.next = null;

        if (current.val < x) {
            if (beforeHead == null) {
                beforeHead = current;
                beforeTail = current;
            } else {
                beforeTail.next = current;
                beforeTail = current;
            }
        } else {
            if (afterHead == null) {
                afterHead = current;
                afterTail = current;
            } else {
                afterTail.next = current;
                afterTail = current;
            }
        }

        current = next;
    }

    if (beforeHead == null) {
        return afterHead;
    }

    beforeTail.next = afterHead;
    return beforeHead;
}

उदाहरण का ट्रेस, x = 5:

देखा नोड	कहाँ गया	बिफोर सूची	आफ्टर सूची
३	बिफोर	३	(खाली)
५	आफ्टर	३	५
८	आफ्टर	३	५ → ८
५	आफ्टर	३	५ → ८ → ५
१०	आफ्टर	३	५ → ८ → ५ → १०
२	बिफोर	३ → २	५ → ८ → ५ → १०
१	बिफोर	३ → २ → १	५ → ८ → ५ → १०

जोड़: 3 → 2 → 1 → 5 → 8 → 5 → 10। मान्य पार्टीशन। (किताब का नमूना हर आधे के अंदर अलग क्रम दिखा सकता है; दोनों ठीक।)

उसी विचार का डमी-नोड रूप: खाली before और after सेंटिनल, हमेशा टेल से जोड़, फिर beforeTail.next = afterHead.next और beforeHead.next लौटाओ। वही जटिलता, थोड़े कम नल चेक।

---

जटिलता

	लागत	क्यों
समय	O(n)	n नोडों पर एक घूमना। हर नोड एक बार जुड़ता है।
अतिरिक्त जगह	O(1)	कुछ पॉइंटर। नोड खुद दोबारा इस्तेमाल होते हैं, नई वस्तु में कॉपी नहीं।

हर नोड देखना ज़रूरी है कि वह किस तरफ जाए, इसलिए रैखिक समय सही निचली सीमा है।

---

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

१. नल या खाली सूची। नल लौटाओ। beforeTail पर क्रैश न हो। २. सभी वैल्यू < x। आफ्टर खाली। बिफोर का हेड लौटाओ। अगर अलग किया तो टेल का next पहले से नल है। ३. सभी वैल्यू >= x। बिफोर खाली। आफ्टर का हेड लौटाओ। ४. एक ही नोड। वैल्यू के हिसाब से कोई भी तरफ। नतीजा वही नोड, next == null। ५. x कई बार। सारी कॉपी आफ्टर तरफ जाती हैं। अलग मध्य सूची नहीं चाहिए। ६. अन्य वैल्यू के साथ डुप्लिकेट। अगर जोड़ते हो तो स्थिरता हर तरफ सापेक्ष क्रम रखती है। पूछें तो ज़ोर से कहो। ७. next को नल करना भूलना। क्लासिक बग: मर्ज के बाद पुरानी चेन कहीं और इंगित करती रहती है, चक्र या गलत टेल बन जाती है। ८. गलती से <= से तुलना। समस्या आमतौर पर बाएँ तरफ सख्त < माँगती है। कोड से पहले असमानता पक्की करो।

---

आम गलतियाँ

• सॉर्ट करके कहना "पार्टीशन कर दिया।" सही लेकिन ज़्यादा, और कमज़ोर आवश्यकता छूटने का संकेत।
• हर वैल्यू के लिए नए नोड बनाना और पुरानी सूची छोड़ देना। अक्सर मौजूदा नोडों पर पॉइंटर सर्जरी चाहिए।
• खाली बिफोर (नल पॉइंटर) या खाली आफ्टर (ठीक अगर टेल पहले से नल) संभाले बिना before को after से जोड़ना।
• लिंक कभी न तोड़ने से afterTail.next पुरानी सूची के बीच में रह जाना।

---

दोस्त को सुना सको, वैसा सार

पार्टीशन हवाई अड्डे की लाइनें हैं, पूरा सॉर्ट नहीं। x से हल्का सब बाएँ। बाकी सब दाएँ।

सूची एक बार घूमो। हर नोड निकालकर बिफोर या आफ्टर चेन में जोड़ो। बिफोर को आफ्टर से चिपकाओ। बायाँ हेड लौटाओ, या अगर बाएँ पर कभी नोड नहीं आया तो दायाँ।

एक पास, कुछ पॉइंटर, कोई नाटक नहीं। अगर अस्थिर क्रम चलता है तो हेड और टेल से बढ़ाना भी काम करता है। साफ़ कहानी और स्थिर आधे चाहिए तो दो सूचियाँ चुनो।

---

अभ्यास

१. चार पॉइंटर से partition याद से लिखो, फिर डमी हेड से। २. कागज़ पर 3 → 5 → 8 → 5 → 10 → 2 → 1 को x = 5 से ट्रेस करो। ३. सब-छोटा और सब-बड़ा इनपुट ट्रेस करो। ४. जानबूझकर current.next = null छोड़कर सही समाधान तोड़ो और चक्र देखो।

सीरीज़ में पिछला: मध्य नोड मिटाना। अगला: सूचियों का योग। पूरा नक्शा: सीटीसीआई जावा।