नोड्स एक यादृच्छिक सूचक

Question

मैं हाल ही में इस दिलचस्प सवाल में आए होने के साथ एक LinkedList पीछे:

"प्रत्येक नोड के साथ लिंक किया हुआ सूची पर विचार करें, एक 'अगले' सूचक भी एक 'यादृच्छिक' सूचक है होने के अलावा में। 'यादृच्छिक' पॉइंटर लिंक किए गए सूची पर कुछ यादृच्छिक अन्य नोड को इंगित करता है। यह न्यूल को भी इंगित कर सकता है। चीजों को सरल बनाने के लिए, कोई भी दो 'यादृच्छिक' पॉइंटर्स एक ही नोड को इंगित नहीं करेगा, लेकिन 1 से अधिक नोड के यादृच्छिक सूचक इंगित कर सकते हैं नल

अब हमें लिंक किए गए सूची के सभी पॉइंटर्स ('अगली' और 'यादृच्छिक' दोनों) की दिशा को उलट करने की आवश्यकता है। बाधा समाधान है (1) अंतरिक्ष जटिलता (एक स्थिर नए नोड्स की संख्या सीआर हो सकती है खाया गया लेकिन सूची की लंबाई के अनुपात में नहीं) "

मैंने इस पर काफी समय बिताया। मैं वास्तव में विश्वास नहीं करता कि यह वास्तव में संभव है।

Answer 1

यह बहुत संभव है। मैं ऐसे समाधान के साथ आया जो संभवतः इष्टतम नहीं है लेकिन दिखाता है कि यह किया जा सकता है। सबसे पहले इसे दो समस्याओं में विभाजित करें: अगले पॉइंटर्स को उलटकर और यादृच्छिक पॉइंटर्स को उलट दें।

पीछे अगला संकेत:

node* last = NULL; 
node* current = head; 
node* next = head->next; 
while (current != NULL) 
{ 
    current->next = last; 
    last = current; 
    current = next; 
    if (current != NULL) 
    next = current->next; 
} 
head = last 

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

node* chainTail = malloc(1); //mallocing here to get a unique pointer 
void reverseRandom(node* rhead) 
{ 
    node* last = chainTail; 
    node* current = rhead; 
    node* next = rhead->random; 
    while (current != NULL) 
    { 
    current->random = last; 
    last = current; 
    current = next; 
    if (current != NULL) 
     next = current->random; 
    } 
} 

हम भी एक सहायक समारोह जरूरत है एक नोड के माता-पिता को खोजने के लिए (या शून्य वापसी अगर वहाँ कोई है)। अब

node* findParent(node* target) 
{ 
    node* candidate = head; 
    while ((candidate != NULL) && (candidate->random != target)) 
    candidate = candidate->next; 
    return candidate; 
} 

हम सिर्फ सूची चलना, किसी भी नोड्स NULL (हमारे श्रृंखला पूंछ) के एक यादृच्छिक मूल्य है मिल जाए, उनके श्रृंखला सिर मिल जाए, और चेन रिवर्स:: हम एक गूंगा रैखिक खोज करेंगे

node* current = head; //Current node in a linear walk looking for chain tails 
while (current != NULL) 
{ 
    if (NULL == current->random) 
    { 
    //current is the tail of a random chain, lets find the head 
    node* curr = current; //Current node in the search for the chain hean 
    node* parent = findParent(curr); 
    while (parent != NULL) 
    { 
     curr = parent; 
     parent = findParent(curr); 
    } 
    //At this point, curr is the head of the random chain, so reverse it 
    reverseRandom(curr); 
    } 
    current = current->next; 
} 

//Clean up chainTail pointers 
node* current; 
for (current = head; current != NULL; current = current->next) 
{ 
    if (current->random == chainTail) 
    { 
    current->random = NULL; 
    } 
} 
free(chainTail); //Stop a memory leak if this is not a global 

मानक अस्वीकरण: मैंने यह कोड नहीं चलाया है। इसमें बग हो सकती है। मुझे अंत के करीब नींद आना शुरू हो गया, इसलिए मैंने एक तार्किक त्रुटि की हो सकती है, लेकिन ऐसा लगता है कि मुझे काम करना है।

इसके अलावा, यदि आप इसे उत्पादन में डाल रहे हैं, तो नहीं। यह कोड ओ (एन^3) के आसपास कहीं चलाता है। यह सबसे तेज़ समाधान नहीं है। यह स्थिर स्थान का उपयोग करता है (हालांकि यहां तक ​​कि शायद इन-अस्तर और आक्रामक परिवर्तनीय साझाकरण द्वारा भी कम किया जा सकता है)।

Answer 2

(Konstantin एन के जवाब पर विस्तार)

आप नहीं फिर से पीछे रहे कुछ भी सुनिश्चित करने के लिए, आप सूची के माध्यम से एक समय में एक नोड कदम सकता है,, बाएं से दाएं, और स्टोर अंतिम जांच नोड की अनुक्रमणिका।

lastIndex <- 0 
cur <- head 

while cur.next not null: 
    if cur.random is null: 
     randomHead <- # use Konstantin N's findParent helper 
     if get_index(randomHead) < lastIndex: 
      # we've already examined it 
     else: 
      # Konstantin N's reverseRandom() 
    cur <- cur.next 
    lastIndex <- lastIndex + 1 

// helper to find node index 
get_index(node): 
    cur <- head 
    ret <- 0 

    while cur.next not null: 
     if cur == node: 
      ret <- ret + 1 
    return ret 

Answer 3

तुम भी इस मामले में जहां यादृच्छिक श्रृंखला रूपों एक (सरल) चक्र के लिए खाते की आवश्यकता होगी। आप चेन के रैखिक ट्रैवर्सल के साथ चक्र का पता लगा सकते हैं; यदि चक्र में नोड्स की संख्या भी होती है तो दोबारा पुन: उलटा होना होगा।

Answer 4

ओ (एन) समय जटिलता के साथ ओ (1) समाधान अंतरिक्ष समाधान पर मेरा प्रयास नीचे दिया गया है।

static Node<E> reverseList(Node<E> head) { 
    if(head == null || head.next == null) { 
    return head; 
    } 

    Node<Integer> current = head; 
    Node temp = null; 

    // Reverse an existing Linked list. 
    while(current != null) { 
    Node previousNext = current.next; 
    current.next = temp; 
    temp = current; 
    current = previousNext; 
    } 

    reversedHead = temp; 
    while(temp != null) { 
    if(temp.jump != null) { 
     Node jumpTemp = temp.jump; 
     jumpTemp.jump = temp; 
     temp.jump = null; 
    } 
    temp = temp.next; 
    } 

    return reversedHead; 
}