排序的LinkedList甚至後奇數元素

我試圖解決這個問題：「安排在一個給定的鏈表的元素，使得所有的偶數號碼奇數後放置元素各自的順序應保持相同的」排序的LinkedList甚至後奇數元素

這是我使用的代碼：

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

這是主要的邏輯：

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算法一點點地解決這一個，如果我遇到奇元素，我首先在sortOddEvenMerger方法中添加它們，甚至在它們後面添加元素。但元素的相對順序發生了變化。

實施例：輸入 - 1 4 5 2

預期輸出 - 1 5 4 2

我的輸出 - 1 5 2 4

如何可以調整它更維持相對順序？

來源

2017-10-16 Aman Grover

你的做法是不僅使問題更加困難比它，但也更低效的，因爲如果我正確認識它，它是O(nlgon)。這是因爲你試圖實現mergesort算法，並且你排序了導致錯誤結果的奇數（甚至是）元素。

一個簡單的算法：

使兩個新的列表（一個用於奇一個用於偶數元件），其最初是空的。
遍歷主列表，並添加您在奇列表，每甚至連名單元素找到每個奇數元素。對於遍歷，這是O(n)，對於每個列表中的每個插入，這是O(1)。
當主列表中沒有元素時，您有兩個列表奇偶，元素具有正確的順序，所以只需鏈接它們以獲得具有預期輸出的一個列表，這一步也是O(1)！

總複雜度：O（n）。（其中n是主列表的長度）。

來源

2017-10-16 13:55:21 coder

當然最後一步是'O（1）'如果你維持奇名單到最後'Node'參考和的頭，甚至列出？ 'oddCurrent.next = evenHead'（當然，應該添加檢查以確保'oddCurrent！= null'，這是可能的）。我猜你認爲'O（n）'是一個錯字。 –

感謝您的評論！其實我完全沒有想過，因爲最後一步O（n）不會改變整體的複雜性，但是你完全正確！（我會再次編輯答案，謝謝!!）。 – coder

就大O而言，但在實踐中是的。我會立刻刪除我的評論，以保持答案的整潔，否則這個問題就會出現。 –

排序的LinkedList甚至後奇數元素

回答

相關問題