Best Possible algorithm to check if two linked lists are merging at any point? If so, where? -

संभव डुप्लिकेट:

यह एक साक्षात्कार प्रश्न है जिसके लिए मेरे पास कोई जवाब नहीं है दो सूचियों को देखते हुए, आप सूची को बदल नहीं सकते हैं और आप लंबाई को नहीं जानते

अगर किसी भी बिंदु पर दो सूचियां मर्ज हो रही हैं तो जांचें:

1. जांचें कि क्या दो सूचियां किसी भी बिंदु पर विलय कर रही हैं?
2. यदि विलय हो रहा है, तो किस बिंदु पर वे विलय कर रहे हैं?
3. यदि मैं आपको सूची को बदलने की अनुमति देता है तो आप अपने एल्गोरिदम को कैसे संशोधित करेंगे?

मुझे यह मानते हुए कि हम साधारण लिंक्ड सूचियों के बारे में बात कर रहे हैं और हम सूची तत्व संकेतकों की एक हैश तालिका को सुरक्षित रूप से बना सकते हैं।

प्रश्न 1: दोनों सूचियों के अंत में विच्छेदन, यदि संबंधित अंतिम तत्व समान हैं सूचियों को कुछ बिंदु पर मिलाएं

जटिलता - ओ (एन) , अंतरिक्ष जटिलता - O (1)

प्रश्न 2:

1. एक सूची के सभी तत्वों को एक हैश तालिका में रखें
2. सूची के प्रत्येक तत्व के लिए हैश तालिका की जांच करने वाली दूसरी सूची में दोहराएं। पहली हिट (यदि कोई हो) मर्ज पॉइंट है, और हमारे पास दूसरी सूची में स्थान है।
3. पहली सूची में स्थिति प्राप्त करने के लिए, पहली सूची पर फिर से दोबारा जानने के लिए उस तत्व की तलाश में पिछले चरण।

समय की जटिलता - O (N) । अंतरिक्ष जटिलता - ओ (एन)

Q3:

1. Q1 के रूप में, लेकिन यह भी सूची संकेतक की दिशा को उल्टा करती है।
2. फिर पिछले सामान्य तत्व की तलाश में उल्लिखित सूचियों को दोहराएं - जो मर्ज बिंदु है - और मूल क्रम में सूची को पुनर्स्थापित कर रहा है।

समय जटिलता - O (N ) । अंतरिक्ष की जटिलता - O (1)