1

リンクリストが与えられた場合、たとえば{1,2,3,5,6,11,10}とすると、{2,6,10,1,3,5,11}として出力する必要があります。偶数は奇数の前に配置する必要があります。

4

8 に答える 8

2

1つの方法は、新しいリストを作成してから最初のリストをループし、新しいリストの最初に偶数を追加し、最後に奇数を追加することです。

于 2012-06-22T05:31:44.183 に答える
2

簡単な解決策は、リストのすべての要素を列挙し、それらを2つの異なるリスト、たとえば、数値の奇数に応じてeven_listとodd_listに割り当てることです。次に、基本的な並べ替えを使用して各リストを個別に並べ替え、最後に2つのリストを新しいリストに連結します。

于 2012-06-22T05:32:13.260 に答える
2

リストを 2 回実行するだけです。

  • 初めてイベントを出力する
  • 2 回目のオッズ出力

これは O(n) になり、コンパレータなどを使用することはできません。

于 2012-06-22T05:36:01.747 に答える
0

操作には を使用する方がよいと思い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]

于 2012-06-22T06:49:53.930 に答える
0

これがアルゴリズム/実装です

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);
}
于 2016-04-08T17:13:44.680 に答える
0
  • temp でヘッド ポインタを取得し、temp を使用してリストをトラバースします
  • 正の数に遭遇したらすぐに、先頭に新しいノードを作成し、データをコピーして、temp が指すノードを削除します。Head は新しいノードを指し、Temp は次のノードを指します。
  • temp->next != NULL までリストをトラバースします
  • 作成と削除の操作は O(1) であるため、時間の複雑さは O(n) になります。
于 2015-01-05T11:01:22.370 に答える
0 
    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);
于 2012-06-22T05:56:26.837 に答える
0

ここでは、値ではなく位置に基づいてノードを配置するロジックを投稿しています。ポインターノードを適切に配置することで、問題に同様のロジックを使用できます。

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;
}
于 2016-05-02T18:20:04.197 に答える