在奇数元素之后对 LinkedList 进行排序

Question

我正在尝试解决这个问题："Arrange elements in a given Linked List such that, all even numbers are placed after odd numbers. Respective order of elements should remain same."

这是我正在使用的代码：

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 方法中添加它们，然后再添加偶数元素。但是元素的相对顺序发生了变化。

Example : Input - 1 4 5 2

Expected output - 1 5 4 2

My output - 1 5 2 4

如何调整它以保持相对顺序？

Answer 1

您的方法不仅使问题变得比实际更难，而且效率也更低，因为如果我理解正确的话，它是 O(nlgon)。这是因为您正在尝试实施归并排序算法并对导致错误结果的奇数（和偶数）元素进行排序。

一个简单的算法：

创建两个最初为空的新列表（一个用于奇数，一个用于偶数）。
遍历主列表并添加您在奇数列表中找到的每个奇数元素和偶数列表中的每个偶数元素。这是 O(n) 遍历和 O(1) 每个列表中的每个插入。
当主列表中没有剩余元素时，您有两个奇偶列表，元素顺序正确，因此只需 link 它们就可以得到一个具有预期输出的列表 - 这一步是 O(1) 还有！

总复杂度：O(n)。（其中 n 是主列表的长度）。

Answer 2

Python 这个问题的代码：

def evenAfterOdd(head):
    if head is None:
        return head
    end = head
    prev = None
    curr = head

    # Get pointer to last Node
    while (end.next != None):
        end = end.next

    new_end = end

    # Consider all even nodes before getting first odd node
    while (curr.data % 2 != 1 and curr != end):
        new_end.next = curr
        curr = curr.next
        new_end.next.next = None
        new_end = new_end.next

    # do following steps only if there is an odd node
    if (curr.data % 2 == 1):

        head = curr

        # now curr points to first odd node
        while (curr != end):

            if (curr.data % 2 == 1):

                prev = curr
                curr = curr.next

            else:

                # Break the link between prev and curr
                prev.next = curr.next

                # Make next of curr as None
                curr.next = None

                # Move curr to odd
                new_end.next = curr

                # Make curr as new odd of list
                new_end = curr

                # Update curr pointer
                curr = prev.next

    # We have to set prev before executing rest of this code
    else:
        prev = curr

    if (new_end != end and end.data % 2 != 1):
        prev.next = end.next
        end.next = None
        new_end.next = end
    return head

在奇数元素之后对 LinkedList 进行排序

Sorting LinkedList with even after odd elements

java

algorithm

mergesort