सीटीसीआई २.६ पैलिंड्रोम लिंक्ड लिस्ट जावा में: दूसरी आधी उलटाओ

टीएल;डीआर

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

पैलिंड्रोम आगे और पीछे एक जैसा पढ़ा जाता है। स्ट्रिंग पर आसान: दोनों सिरों पर पॉइंटर, बीच की ओर चलो। एक-दिशा लिंक्ड लिस्ट सिर्फ आगे चलती है। prev नहीं, और बीच का नोड ढूंढना पूरा स्कैन मांगता है। इसलिए इंटरव्यू वाला सवाल "क्या यह लिस्ट पैलिंड्रोम है?" तुम्हें वह ढांचा खुद बनाना सिखाता है जो मुफ्त में नहीं मिलता।

यह क्रैकिंग द कोडिंग इंटरव्यू शैली सेट की समस्या २.६ है (लिंक्ड लिस्ट)। मूल शिक्षण, किताब की नकल नहीं।

---

रोजमर्रा की तस्वीर

लंबी टेप पर चिपकने वाले नोट्स की कतार सोचो: 1 → 2 → 3 → 2 → 1। जानना है कि टेप को बीच से मोड़ने पर हर नोट अपने दर्पण से मिलेगा या नहीं।

पूरी टेप पलट नहीं सकते, वरना पहली आधी का क्रम खो जाएगा। व्यावहारिक कदम:

१. मोड़ ढूंढो (लिस्ट का मध्य)। २. सिर्फ दूसरी आधी पलटो ताकि वह मध्य की ओर इंगित करे। ३. सिरे से और उलटी हुई आधी के नए सिरे से दोनों तरफ चलो। हर जोड़ी के मान मिलने चाहिए। ४. अगर लिस्ट पहले जैसी चाहिए, दूसरी आधी फिर से पलटकर जोड़ दो।

पूरा प्लान: मध्य खोजो, दूसरी आधी उलटाओ, मिलाओ, जरूरत हो तो पुनर्स्थापित करो।

---

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

इनपुट: पूर्णांक मान वाले नोड्स की एक-दिशा लिंक्ड लिस्ट का हेड (या कोई तुलनीय डेटा)।

आउटपुट: true अगर मानों का क्रम पैलिंड्रोम है; वरना false।

उदाहरण

लिस्ट	उत्तर	क्यों
1 → 2 → 2 → 1	true	सम लंबाई; दोनों आधी मिलती हैं
1 → 2 → 3 → 2 → 1	true	विषम लंबाई; केंद्र 3 अकेला
1 → 2 → 3	false	सिरे नहीं मिलते
7	true	एक नोड
खाली / null	true (सामान्य शिक्षण विकल्प)	खाली क्रम पैलिंड्रोम है

इंटरव्यू में साफ करो

• क्या लिस्ट अस्थायी रूप से बदल सकते हो? (यह हल बदलता है, फिर वापस करता है।)
• नल और खाली: true या एक्सेप्शन?
• मान: सिर्फ अंक, या सामान्य पूर्णांक?

तुम बूलियन लौटाते हो। रिवर्स छापने या नई लिस्ट बनाने को अंतिम उत्तर नहीं कहा गया।

---

कोड से पहले सोचना

स्टैक या कॉपी (ठीक, मुख्य नहीं)

हर मान स्टैक पर धकेलो, या ऐरे में कॉपी करो, फिर हेड से दूसरी बार मिलाओ। समय ओ(एन), अतिरिक्त जगह ओ(एन)। जिक्र करो। अक्सर अगला सवाल बेहतर जगह का होता है।

रिकर्सिव तुलना भी चलती है और साफ लगती है, पर लंबी लिस्ट पर कॉल स्टैक फिर भी ओ(एन) है। जगह की वही श्रेणी जो स्टैक वाले हल की।

मुख्य तरीका: दूसरी आधी उलटाओ (अतिरिक्त जगह ओ(१))

१. मध्य खोजो दो पॉइंटर से: slow एक नोड, fast दो नोड। जब fast दो कदम और नहीं ले सकता, slow पहली आधी के अंत पर (सम लंबाई) या केंद्र पर (विषम लंबाई) होता है। २. उलटाओ वह लिस्ट जो slow.next से शुरू होती है। क्लासिक तीन-पॉइंटर रिवर्स: prev, curr, next। ३. मिलाओ head से और उलटी दूसरी आधी से, नोड-दर-नोड, जब तक दूसरी आधी खत्म न हो। विषम लंबाई पर केंद्र किसी जोड़ी से नहीं मिलता, और यह सही है। ४. पुनर्स्थापित (वैकल्पिक पर साफ): दूसरी आधी फिर उलटाओ और slow.next पर जोड़ो ताकि कॉलर मूल क्रम देखे।

क्यों काफी है: पैलिंड्रोम केंद्र के इर्द-गिर्द मिलती जोड़ों से परिभाषित होता है। पिछली आधी उलटी के बाद वे जोड़ें दो आगे की सैर पर एक-दूसरे के सामने आ जाती हैं।

---

जावा हल: मध्य, रिवर्स, तुलना, पुनर्स्थापना

public class LinkedListPalindrome {

    public static class ListNode {
        int val;
        ListNode next;

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

    /**
     * Returns true if the list values form a palindrome.
     * Temporarily reverses the second half, then restores it.
     */
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 1. Middle: slow ends at end of first half (even) or at center (odd)
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. Reverse second half
        ListNode secondHalf = reverse(slow.next);

        // 3. Compare first half with reversed second half
        ListNode p1 = head;
        ListNode p2 = secondHalf;
        boolean ok = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                ok = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 4. Restore list
        slow.next = reverse(secondHalf);
        return ok;
    }

    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome(list(1, 2, 2, 1)));       // true
        System.out.println(isPalindrome(list(1, 2, 3, 2, 1)));    // true
        System.out.println(isPalindrome(list(1, 2, 3)));          // false
        System.out.println(isPalindrome(list(7)));                // true
        System.out.println(isPalindrome(null));                   // true
    }

    private static ListNode list(int... vals) {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        for (int v : vals) {
            t.next = new ListNode(v);
            t = t.next;
        }
        return dummy.next;
    }
}

चलकर देखो: 1 → 2 → 3 → 2 → 1

कदम	क्या होता है
मध्य	slow 3 (केंद्र) पर रुकता है। fast दो कदम और नहीं ले सकता।
उलटा	दूसरी आधी 2 → 1 बन जाती है 1 → 2। आकार: पहली आधी अभी भी 1 → 2 → 3, फिर उलटी पूंछ।
तुलना	1 बनाम 1, 2 बनाम 2। दूसरी आधी खत्म। मिलान।
पुनर्स्थापना	1 → 2 फिर 2 → 1 बनकर 3 के बाद जुड़ता है। मूल लिस्ट फिर।

चलकर देखो: 1 → 2 → 2 → 1 (सम)

कदम	क्या होता है
मध्य	लूप शर्त slow को पहले 2 पर रोकती है (पहली आधी का अंत)।
उलटा	दूसरी आधी 2 → 1 बनती है 1 → 2।
तुलना	1 बनाम 1, 2 बनाम 2। मिलान।
पुनर्स्थापना	दूसरी आधी वापस जोड़ो।

विषम लंबाई तुलना में केंद्र छोड़ती है। सम लंबाई दो बराबर आधी मिलाती है। एक ही कोड पथ दोनों संभालता है।

---

समय और जगह

तरीका	समय	अतिरिक्त जगह	नोट
दूसरी आधी उलटाओ	ओ(एन)	ओ(१)	मुख्य उत्तर; बदलकर फिर ठीक
मानों का स्टैक	ओ(एन)	ओ(एन)	सरल; अच्छा पहला मसौदा
ऐरे कॉपी + दो पॉइंटर	ओ(एन)	ओ(एन)	स्टैक जैसा ही विचार
रिकर्शन (अंतर्निहित स्टैक)	ओ(एन)	ओ(एन) कॉल फ्रेम	साफ कोड, स्थिर जगह नहीं

मध्य एक पास। उलटा आधी लिस्ट के अनुपात में। तुलना एक और आधा पास। पुनर्स्थापना एक और रिवर्स। कुल रैखिक, सिर्फ स्थिर अतिरिक्त पॉइंटर।

---

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

• विषम लंबाई: केंद्र नोड की जोड़ी नहीं। उससे कुछ मत मिलाओ। ऊपर की मध्य तर्क उसे पहली आधी में छोड़ती है और रिवर्स slow.next से शुरू करती है।
• सम लंबाई: दो बराबर आधी। वही लूप; कोई बचा केंद्र नहीं।
• एक नोड: जल्दी true।
• दो नोड: 1 → 1 सच; 1 → 2 झूठ। मध्य slow को पहले नोड पर रखता है; एक जोड़ी उलटी और मिलाई जाती है।
• नल हेड: true मानो (या परिभाषा तय करो और उसी पर टिको)।
• स्थायी बदलाव मना: तुलना के बाद पुनर्स्थापित करो। अगर कोई भी म्यूटेशन मना हो, स्टैक/कॉपी पर जाओ और बोलो।
• साझा संरचना / साथ-साथ पाठक: थोड़ी देर का बदलाव भी असुरक्षित। अगर लिस्ट साझा है तो साफ कहो।

यहां आधी गलतियां मध्य का एक-नोड आगे-पीछे (रिवर्स गलत नोड से) और मूल लिस्ट जरूरी होने पर पुनर्स्थापना भूलना हैं।

---

आम गलतियां

१. स्ट्रिंग वाले दो-पॉइंटर सोच बिना एक-दिशा लिस्ट पर पीछे जाने का तरीका। २. गलत मध्य: सम लंबाई पर केंद्र से उलटाकर लंबाइयां बिगाड़ना। ३. पुनर्स्थापना भूलना विनाशकारी रिवर्स के बाद। ४. दूसरी आधी से आगे तुलना या केंद्र को जुड़वां समझना। ५. ओ(१) जगह का दावा रिकर्शन पर, कॉल स्टैक बिना माने।

---

दोस्त को समझाओ

एक-तरफा मानों की श्रृंखला मिली। क्या आगे-पीछे एक जैसी पढ़ी जा सकती है?

बीच से मोड़ो। सिर्फ पिछली आधी पलटो। आगे से और उलटी पिछली आधी से चलो: हर जोड़ी मिलनी चाहिए। श्रृंखला वापस चाहिए तो पिछली आधी फिर पलटो।

जावा में: मध्य के लिए धीमा/तेज, दूसरी आधी उलटाओ, मिलाओ, साफ करने के लिए फिर उलटाओ। समय ओ(एन), अतिरिक्त जगह ओ(१)। स्टैक भी चलता है अगर अतिरिक्त मेमोरी ठीक हो।

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