java - 如何在链表中将所有偶数排列在奇数前面

Question

给定一个链表，比如 {1,2,3,5,6,11,10}，我需要输出为 {2,6,10,1,3,5,11}。偶数需要排在奇数之前。

Answer 1

一种方法是创建一个新列表，然后循环遍历第一个列表，将偶数添加到新列表的开头，奇数添加到末尾。

Answer 2

一个简单的解决方案是枚举列表的所有元素并将它们分配给两个不同的列表，例如 even_list 和odd_list，具体取决于数字的奇数。然后使用基本排序对每个列表进行单独排序，最后将两个列表连接成一个新列表。

Answer 3

我只浏览了两次列表：

• 第一次通过输出偶数
• 第二次通过输出赔率

这将是 O(n)，使用比较器等可能不是。

Answer 4

• 在 temp 中获取头指针并使用 temp 遍历列表
• 一旦遇到正数，就在头部创建一个新节点，复制数据并删除 temp 指向的节点。Head 将指向新节点，Temp 将指向下一个节点。
• 遍历列表直到 temp->next != NULL
• 时间复杂度将是 O(n)，因为创建和删除操作是 O(1)

Answer 5

    LinkedList<Integer> list = new LinkedList<Integer>();
    LinkedList<Integer> newlist = new LinkedList<Integer>();
    int[] a = {1,2,3,5,6,11,10};
    for(int i=0;i<a.length;i++) {
        list.add(a[i]);
    }

    for(int i=0,j=0; i<list.size(); i++) {
        if(a[i]%2 == 0) {
            newlist.add(j++, a[i]);
        } else {
            newlist.addLast(a[i]);
        }
    }

    System.out.println(newlist);

Answer 6

我认为为了更好地使用操作ArrayList，您可以参考以下返回排序列表的方法。

public static List<Integer> sortList(List<Integer> list){
    LinkedList<Integer> sortedList = new LinkedList<Integer>();

    List<Integer> evenList=new ArrayList<Integer>();
    List<Integer> oddList=new ArrayList<Integer>();
    for(Integer i:list){

        if(i%2==0)
            evenList.add(i);
        else
            oddList.add(i);
    }

    Collections.sort(evenList);
    Collections.sort(oddList);
    sortedList.addAll(evenList);
    sortedList.addAll(oddList);


    return sortedList;
}

输入：

[1, 2, 3, 5, 6, 11, 10]

输出：

[2, 6, 10, 1, 3, 5, 11]

Answer 7

在这里，我发布了一个基于位置而不是值来排列节点的逻辑。您可以通过适当地放置指针节点来为您的问题使用类似的逻辑。

public ListNode oddEvenList(ListNode head) {
//if null 
 if(head == null) return null;

//only one/two node/s present
 if(head.next == null || head.next.next == null) return head;

ListNode even = head, odd = even.next, res = odd;
while(odd!=null && even.next != null && odd.next != null){
    even.next = odd.next;
    even = even.next;
    odd.next = even.next;
    odd = odd.next;
    even.next = res;
}
return head;
}

Answer 8

这是算法/实现

public static LinearNode<Integer> seperateEvenAndOddNodes(LinearNode<Integer> head) {
    LinearNode<Integer> tail = head, prevNode=null, currNode = head, nextNode;
    int length = length(head), count = 0;
    boolean allEven = true, allOdd = true;
    //point to the last node, start dumping all nodes after this
    while (tail.next() != null) {
        if (tail.getElement() % 2 == 0) {
            allOdd = false;
        } else {
            allEven = false;
        }
        tail = tail.next();
    }
    // Dont do anything if either all odd or all even
    if (allOdd || allEven) {
        return head;
    }
    // Make sure you don't go in infinite loop, and hence condition to make sure, you traverse limited nodes.
    while (currNode != null && count < length) {
        nextNode = currNode.next();
        //move currNode to the end of list, if it is odd.
        if (currNode.getElement() % 2 == 1) {
            LinearNode<Integer> temp = currNode;
            if (prevNode != null) {
                prevNode.next(nextNode);
                currNode = prevNode;
            } else {
                head = nextNode;
                currNode = null;
            }
            tail.next(temp);
            tail = temp;
            temp.next(null);
        }
        prevNode = currNode;
        currNode = nextNode;
        count++;
    }
    //return the new head, in case the list begins with odd
    return head;
}

这是单元测试

@Test
public void seperateEvenAndOddNodesTest() {
    LinearNode<Integer> head = buildLinkedList(2,3,4,1,7,8,9);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 2,4,8,3,1,7,9);

    head = buildLinkedList(9,3,4,1,7,8,2);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 4,8,2,9,3,1,7);


    head = buildLinkedList(1,3,5,7);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 1,3,5,7);

    head = buildLinkedList(2,4,6,8);
    head = LinkedListUtil.seperateEvenAndOddNodes(head);
    assertLinkedList(head, 2,4,6,8);
}