बिना लिंक के लिंक्ड सूची रिवर्स

Question

क्या सी में अस्थायी चर का उपयोग किए बिना लिंक सूची को रिवर्स करने का कोई तरीका है? अग्रिम धन्यवाद।

प्रसिद्ध दृष्टिकोण:

Element *reverse(Element *head) 
{ 
    Element *previous = NULL; 

    while (head != NULL) { 
     // Keep next node since we trash 
     // the next pointer. 
     Element *next = head->next; 

     // Switch the next pointer 
     // to point backwards. 
     head->next = previous; 

     // Move both pointers forward. 
     previous = head; 
     head = next; 
    } 

    return previous; 
} 

का उपयोग करता अस्थायी चर

सौरभ

Answer 1

ध्यान रखें कि आपके temp उपयोग वास्तव में दो swap() कॉल पैदा कर रहा है, और साथ बदला जा सकता:

swap(head->next,previous); 
swap(previous,head); 

आप XOR का उपयोग कर अस्थायी कर्मियों के बिना स्वैप कर सकते हैं, यह xor swap कहा जाता है।

Answer 2

उपयोग XOR-swaps नकली करने के संकेत दिए गए एक XOR-linked-list.

कार्यान्वयन एक व्यायाम के रूप पाठक के लिए छोड़ दिया जाता है पर ।

Answer 3

रिकर्सिव दृष्टिकोण: पुनरावर्ती क्रिया के लिए

Element *reverse(Element *head, Element **first) 
{ 
    if (head->next == NULL) 
    { 
     *first = head; 
     return head; 
    } 


    Element* NextElement= reverse (head->next, first); 
    NextElement->next = head; 
    head->next = null; 

    return head; 
} 

कॉल:

Element *revLinkListHead; 
    reverse(head, &revLinkListHead); 

Answer 4

कोई अभी भी रुचि है, तो यहाँ समाधान सभी में कोई नया चर का उपयोग करता है, पुनरावर्ती में पारित छोड़कर उन है कहते हैं।

public static List invert(List l) { 
    invert(l.next, l, l); 
    l = l.next; 
    breakCycle(l, l); 
    return l; 
} 

private static void invert(List l, List toBeNext, List first) { 
    if(l.next == null) { 
     l.next = toBeNext; 
     first.next = l; 
    } else { 
     invert(l.next, l, first); 
     l.next = toBeNext; 
    } 
} 

private static void breakCycle(List l, List first) { 
    if(l.next == first) { 
     l.next = null; 
    } else { 
     breakCycle(l.next, first); 
    } 
} 

विचार निम्नलिखित है: सबसे पहले हम की विपरीत समारोह रिकर्सिवली चलाते हैं, और इसे लागू इसलिए जब यह पिछले तत्व यह वर्तमान प्रधान के अगले तत्व के रूप में यह प्रदान करती है (पैरामीटर first) तक पहुँच जाता है। हमने इसे निष्पादित करने के बाद, हमारे पास एक उलटा सूची होगी लेकिन साइकिल चलाना होगा, इसलिए वर्तमान head.next उल्टा सूची के प्रमुख पर इंगित करेगा। हम अपने अगले तत्व (उल्टा सूची के वास्तविक सिर) में सिर को फिर से सौंपते हैं, और आखिरी चीज हमें चक्र को तोड़ना है। तो हम breakCycle पर कॉल करते हैं जो नौकरी को दोबारा काम करता है!