0

私は次の問題を解決しようとしています

すべての負の値がすべての非負の値の前に表示されるように、リストの要素を再配置するメソッド split を記述します。たとえば、変数リストに次の一連の値が格納されているとします。

[8, 7, -4, 19, 0, 43, -8, -7, 2]

list.split(); の呼び出し リストを並べ替えて、ネガを最初に配置する必要があります。1 つの考えられる配置は次のとおりです。

[-4, -8, -7, 8, 7, 19, 0, 43, 2]

しかし、ネガが非ネガの前に現れることだけが重要です。したがって、これは可能な解決策の 1 つにすぎません。別の合法的な解決策は、次のように値を再配置することです。

[-7, -8, -4, 2, 43, 0, 19, 7, 8]

この問題を解決するために、データ フィールドを交換したり、新しいノードを作成したりすることはできません。リストのリンクを並べ替えて、リストを並べ替える必要があります。この問題を解決するために、配列、ArrayList、スタック、キューなどの補助構造を使用することもできません。

私はこの問題を解決する方法について本当に無知です。私が考えているアプローチの 1 つは、負のデータを持つノードを特定して先頭に追加することですが、このアプローチをコーディングする方法がわかりません。これが私のリストクラスです。

public class LinkedList {

// The Linked List's Node structure
   static class Node {
    private Node next;
    private int data;

    Node(int data) {
        this.data = data;
        next = null;
    }

    public int getData() {
        return data;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

}

private Node head;
private int size;

public void setHead(Node head) {
    this.head = head;
}

public int getSize() {
    return size;
}

public Node getHead() {
    return head;
}

public LinkedList() {
    head = null;
    size = 0;
}
}

この問題に取り組むためのヒント/提案はありますか?

@nishu が提案したように、次の解決策を思いつきました。できます。

public Node delete(int data) {

    Node del = null;
    Node tmp = head;
    if (head.getData() == data) {
        Node tmp2 = head;
        Node nxt = tmp.getNext();
        tmp2.setNext(null);
        this.setHead(nxt);
        del = tmp2;
    } else if (isLast(data)) {
        while (true) {
            if (tmp.getNext().getNext() == null) {
                del = tmp.getNext();
                tmp.setNext(null);
                break;
            }
            tmp = tmp.getNext();
        }
    } else {
        while (tmp != null && tmp.getNext() != null) {
            if (tmp.getNext().getData() == data) {
                Node prev = tmp;
                del = tmp.getNext();
                Node nextOfToBeDeleted = tmp.getNext().getNext();
                prev.setNext(nextOfToBeDeleted);
                break;
            }
            tmp = tmp.getNext();
        }
    }
    return del;
}

public void addToFront(Node node) {
    node.setNext(head);
    this.setHead(node);
}

public void split() {

    Node tmp = head;
    Node del = null;
    while (tmp != null) {
        if (tmp.getData() < 0) {
            Node nxt = tmp.getNext();
            del = delete(tmp.getData());
            addToFront(del);
            while (tmp != nxt) {
                tmp = tmp.getNext();
            }
        } else {
            tmp = tmp.getNext();
        }

    }
}

public boolean isLast(int data) {
    boolean last = false;
    Node tmp = head;
    while (true) {
        if (tmp.getData() == data && tmp.getNext() != null) {
            last = false;
            break;
        } else if (tmp.getNext() == null && tmp.getData() == data) {
            last = true;
            break;
        }
        tmp = tmp.getNext();
    }
    return last;
}
4

2 に答える 2

1

Add a new interface to your node type:

static Node<T> implements Iterable<Node<T>> {
    private Node<T> next;
    private T data;

    public T getData() {return data;}
    public void setData(int data) {this.data = data;}

    public Node getNext() {return next;}
    public void setNext(Node<T> next) {this.next = next;}
}

The NodeIterator can then be

NodeIterator<E extends Node<T>, L extends LinkedList<T>> implements Iterator<E>{
    E last, current; L parent;
    public NodeIterator(E node, L parent){this.current = node; this.parent = parent;}
    @Override public boolean hasNext(){return current.getNext() != null}
    @Override public E next(){last = current; current = current.getNext(); return last;}
    @Override public void remove(){last.setNext(current = current.getNext()); parent.size--;}
}

Now that you have this, you can write the method for moving the list:

public class LinkedList<E> {

    private Node<E> head;
    private int size;

    public void insertAtHead(Node<E> node){
        node.setNext(head);
        head=node;
        size++;
    }

    public void split(Predicate<E> condition){
        Iterator<Node<E>> it = nodeIterator();
        while(it.hasNext()){
            Node<E> node = it.next();
            if(condition.test(node.getData())){
                it.remove();
                insertAtHead(node);
            }
        }
    }

    public Iterator<Node<E>> nodeIterator() {
        return new NodeIterator<Node<E>, LinkedList<E>>(parent, head);
    }
}

Invoke like this:

LinkedList<Integer> list = new LinkedList<>();
 // [... add stuff to list ...]
list.split((Integer i) -> i < 0);

EDIT: fixed the code so it will correctly update the list's size when the iterator's remove function is called. (Still works only with nodes that are contained in one list, though. If two list instances incorporate the same nodes, and one of their shared nodes is removed, only one will have its size updated.)

于 2013-11-11T15:53:12.800 に答える