विचित्र तत्वों के बाद भी लिंक किए गए लिस्ट को

Question

मैं इस प्रश्न को हल करने की कोशिश कर रहा हूं: "किसी दिए गए लिंक किए गए सूची में तत्वों को व्यवस्थित करें, जैसे कि सभी संख्याएं विषम संख्याओं के बाद भी रखी जाती हैं। तत्वों का प्रासंगिक क्रम समान होना चाहिए।"

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

    Node<Integer> middle = getMiddle(head); 
    Node<Integer> nextOfMiddle = middle.next; 

    middle.next = null; 

    Node<Integer> temp1 = sortOddEven(head); 
    Node<Integer> temp2 = sortOddEven(nextOfMiddle); 

    Node<Integer> sortedList = sortOddEvenMerger(temp1, temp2); 
    return sortedList; 
} 

static Node<Integer> sortOddEvenMerger(Node<Integer> head1, Node<Integer> head2) { 
    Node<Integer> head3 = null, tail3 = null; 

    if(head1.data.intValue()%2 != 0) { 
     head3 = head1; 
     tail3 = head1; 

     head1 = head1.next; 
    } else { 
     head3 = head2; 
     tail3 = head2; 

     head2 = head2.next; 
    } 

    while(head1 != null || head2 != null) { 

     if(head1 == null) { 
      tail3.next = head2; 

      return head3; 
     } else if(head2 == null){ 
      tail3.next = head1; 

      return head3; 
     } 

     if(head1.data.intValue()%2 != 0) { 
      tail3.next = head1; 
      tail3 = tail3.next; 

      head1 = head1.next; 
     } else { 
      tail3.next = head2; 
      tail3 = tail3.next; 

      head2 = head2.next; 
     } 

    } 

    tail3.next = null; 

    return head3; 
} 

मूल रूप से मैं बदलाव है MergeSort एल्गोरिथ्म एक छोटा सा यह एक हल करने के लिए, अगर मैं अजीब मुठभेड़:

class Node<T> { 
    T data; 
    Node<T> next; 
    Node(T data) { 
     this.data = data; 
    } 
} 

यह मुख्य तर्क है:

इस कोड मैं का उपयोग कर रहा है तत्व, मैं उन्हें sortOddEvenMerger विधि में और बाद में तत्वों में भी जोड़ता हूं। लेकिन तत्वों के सापेक्ष क्रम बदल जाते हैं।

उदाहरण: इनपुट - 1 4 5 2

अपेक्षित उत्पादन - 1 5 4 2

मेरे उत्पादन - 1 5 2 4

मैं कैसे इसे और अधिक tweak बनाए रखने के लिए कर सकते हैं सापेक्ष आदेश?

Answer 1

आपका दृष्टिकोण न केवल समस्या को और अधिक कठिन बना रहा है बल्कि यह भी अधिक अक्षम है क्योंकि यदि मैं इसे सही ढंग से समझ रहा हूं तो यह O(nlgon) है। ऐसा इसलिए है क्योंकि आप विलय एल्गोरिदम लागू करने की कोशिश कर रहे हैं और आप अजीब (और यहां तक ​​कि) -मेंट्स को सॉर्ट करते हैं जो गलत परिणाम लेते हैं।

एक साधारण एल्गोरिथ्म:

• दो नई सूचियों जो शुरू में खाली हैं (यहां तक ​​कि तत्वों के लिए अजीब एक के लिए एक) बनाओ।

• मुख्य सूची को पार करें और विषम सूची में पाए गए हर विषम तत्व को जोड़ें और यहां तक ​​कि सूची में भी हर तत्व जोड़ें। प्रत्येक सूचियों में प्रत्येक सम्मिलन के लिए यह O(n) ट्रैवर्सल और O(1) है।

• जब मुख्य सूची में कोई तत्व नहीं छोड़ा जाता है तो आपके पास दो सूचियां होती हैं-यहां तक ​​कि सही क्रम वाले तत्वों के साथ भी, इसलिए उन्हें अपेक्षित आउटपुट के साथ एक सूची प्राप्त करने के लिए लिंक करें- यह चरण O(1) भी है!

कुल जटिलता: ओ (एन)। (जहां एन मुख्य सूची की लंबाई)।