Перегруппировка связанного списка

Question

Я пытаюсь решить следующую задачу

Написать раскол метода, который переставляет элементы списка так, что все отрицательных значений появляются перед всеми не-негативами. Например, предположим, что переменная хранит список следующую последовательность значений:

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

Answer 1

Следуйте процедуре идти дальше:

1. создать методы: вставки и удаления. Вставить - вставить данные в начале. delete - он будет искать переданное значение и удалять первое вхождение элемента в списке и возвращает удаленный узел.

2. Начать перемещение по связанному списку. Всякий раз, когда вы обнаруживаете отрицательный узел, удалите его из существующего связанного списка и вызовите метод вставки на узле, возвращаемом функцией удаления.

Answer 2

Добавить новый интерфейс для вашего типа узла:

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

EDIT: фиксированный код так будет правильно обновлять размер в списке, когда функция удалить итератора называется. (Тем не менее, работает только с узлами, которые содержатся в одном списке. Если два экземпляра списка содержат одни и те же узлы, а один из их общих узлов удален, только один будет обновлен его размер.)