0

我正在尝试解决以下问题

编写一个方法 split 重新排列列表的元素，使所有负值出现在所有非负值之前。例如，假设一个变量列表存储以下值序列：

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

list.split() 的调用；应该重新排列列表以将否定放在首位。一种可能的安排如下：

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

但重要的是，否定出现在非否定之前。所以这只是一种可能的解决方案。另一种合法的解决方案是以这种方式重新排列值：

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

不允许交换数据字段或创建任何新节点来解决此问题；您必须通过重新排列列表的链接来重新排列列表。您也可能不使用数组、ArrayLists、堆栈、队列等辅助结构来解决此问题。

我真的不知道如何解决这个问题。我正在考虑的一种方法是识别具有负数据的节点并将其添加到头部，但我无法弄清楚如何编写这种方法。这是我的列表类。

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

2

按照程序走得更远：

  1. 创建方法：插入和删除。insert - 它将在开头插入数据。delete - 它将搜索传递的值并删除列表中第一次出现的项目并返回被删除的节点。

  2. 开始遍历链表。每当找到一个负节点时，将其从现有链表中删除，并在删除函数返回的节点上调用 insert 方法。

于 2013-11-11T15:35:19.047 回答
1

为您的节点类型添加一个新接口：

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;}
}

然后NodeIterator可以

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--;}
}

现在你有了这个，你可以编写移动列表的方法：

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);
    }
}

像这样调用：

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

编辑：修复了代码，以便在调用迭代器的删除函数时正确更新列表的大小。（但仍然只适用于包含在一个列表中的节点。如果两个列表实例包含相同的节点，并且它们的一个共享节点被删除，那么只有一个的大小会更新。）

于 2013-11-11T15:53:12.800 回答