排序的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甚至后奇数元素

回答

相关问题