Добавить двусвязному список узлов в односвязный список

Question

Данный односвязанны список: 1 -> 2 -> 3 -> 4 -> 5 -> null
Modify средний элемент как дважды связанный список Node
здесь средний элемент 3
3 -> next должен указывать на 4
3 -> prev должен указывать на 1

Может ли кто-нибудь предложить, как это можно сделать? интервьюер дал мне подсказку use interface. но я не мог понять, как это сделать.
Мне нужно перебрать этот связанный список и распечатать весь узел, а когда он достигнет середины, напечатать, где следуют, а затем - prev, а затем распечатать до конца списка.
Expected output: 1, 2, Middle: 3, Prev: 1, Next: 4, 5

У меня возникла проблема с добавлением среднего узла.

Answer 1

Итак, это «работает», но если на интервью ожидается ответ, это слишком много работы.

LinkedList

public class LinkedList { 

    public interface Linkable<V, L extends Linkable> { 
     V getValue(); 
     L getNext(); 
     void setNext(L link); 
    } 

    public static class Node implements Linkable<Integer, Linkable> { 
     int value; 
     Linkable next; 

     Node(int value) { 
      this.value = value; 
     } 

     @Override 
     public Integer getValue() { 
      return value; 
     } 

     @Override 
     public Linkable getNext() { 
      return next; 
     } 

     @Override 
     public void setNext(Linkable link) { 
      this.next = link; 
     } 
    } 

    private Linkable head; 

    public boolean isEmpty() { 
     return this.head == null; 
    } 

    public Linkable getHead() { 
     return head; 
    } 

    public void add(int v) { 
     Node next = new Node(v); 
     if (isEmpty()) { 
      this.head = next; 
     } else { 
      Linkable tmp = this.head; 
      while (tmp.getNext() != null) { 
       tmp = tmp.getNext(); 
      } 
      tmp.setNext(next); 
     } 
    } 
} 

---

Интерфейс

interface DoublyLinkable<V, L extends LinkedList.Linkable> extends LinkedList.Linkable<V,L> { 
    LinkedList.Linkable getPrev(); 
    void setPrev(LinkedList.Linkable prev); 
} 

DoubleNode

public class DoubleNode extends LinkedList.Node implements DoublyLinkable<Integer, LinkedList.Linkable> { 
    LinkedList.Linkable prev; 

    public DoubleNode(int value) { 
     super(value); 
    } 

    @Override 
    public LinkedList.Linkable getPrev() { 
     return prev; 
    } 

    @Override 
    public void setPrev(LinkedList.Linkable prev) { 
     this.prev = prev; 
    } 
} 

---

Драйвер

Выходы

1, 2, Middle: 3, Prev: 1, Next: 4, 5 

---

public class Driver { 

    public static LinkedList getList() { 
     LinkedList list = new LinkedList(); 
     for (int i = 1; i <= 5; i++) { 
      list.add(i); 
     } 
     return list; 
    } 

    public static void main(String[] args) { 

     LinkedList list = getList(); 

     LinkedList.Linkable head = list.getHead(); 
     LinkedList.Linkable beforeMiddle = null; 
     LinkedList.Linkable middle = list.getHead(); 
     LinkedList.Linkable end = list.getHead(); 

     if (head != null) { 
      // find the middle of the list 
      while (true) { 
       if (end.getNext() == null || end.getNext().getNext() == null) break; 

       beforeMiddle = middle; 
       middle = middle.getNext(); 

       end = end.getNext().getNext(); 
      } 

      // Replace middle by reassigning the pointer to it 
      if (beforeMiddle != null) { 

       DoubleNode n = new DoubleNode((int) middle.getValue()); // same value 
       n.setPrev(list.getHead()); // point back to the front 
       n.setNext(middle.getNext()); // point forward to original value 

       beforeMiddle.setNext((DoublyLinkable) n); 
       middle = beforeMiddle.getNext(); 
      } 

      // Build the "expected" output 
      StringBuilder sb = new StringBuilder(); 
      final String DELIMITER = ", "; 
      head = list.getHead(); 
      boolean atMiddle = false; 
      if (head != null) { 
       do { 
        if (head instanceof DoublyLinkable) { 
         atMiddle = true; 
         String out = String.format("Middle: %d, Prev: %d, ", (int) head.getValue(), (int) ((DoublyLinkable) head).getPrev().getValue()); 
         sb.append(out); 
        } else { 
         if (atMiddle) { 
          sb.append("Next: "); 
          atMiddle = false; 
         } 
         sb.append(head.getValue()).append(DELIMITER); 
        } 

        head = head.getNext(); 
       } while (head != null); 
      } 
      sb.setLength(sb.length() - DELIMITER.length()); 

      System.out.println(sb.toString()); 
     } 

    } 
} 

Answer 2

Если вы этого не сделали, вам лучше определить функцию length(), поэтому заданный один связанный список вы можете узнать, сколько у него узлов.

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

Теперь я предполагаю, что вы определили две структуры (Struct, Class или что-то другое в зависимости от языка, который вы используете). Итак, скажем, у вас есть Node_s, определяемый как узел с указателем next, и Node_d с next и указателем prev. (Node_d может наследовать от Node_s, поэтому вам нужно добавить атрибут prev в дочернем классе). Зная это, приведенный выше код должен делать то, что вам нужно:

функция do_it (my_LinkedList LinkedList) {

int i_middle; 
    int length = linkedList.length(); 

    if ((length ÷ 2) != 0) i_middle = length/2; 
    else return -1; 

    Node_s aux = linkedList.first(); 
    int index = 0; 
    Node_d middle= null; 

    while (aux != null) { 

     if (index == i_middle - 1){ //now aux is the middle's previous node 

      middle.data = aux.next.data; //aux.next is the middle singly node, we assignate the data to the new double linked node 

      middle.prev = aux; //as we said, aux is the prev to the middle 
      midle.next = aux.next.next; //so aux.next.next is the next to the middle 
      print(what you need to print); 
     }else { 
      print("Node " + index " next: "+ aux.next); 
     }//end if 

     index++; 
     aux = aux.next; 
    } //end while 

}//end function 

Этот предыдущий код должен делать то, что вам нужно. Я написал ответ в каком-то псевдо-Java-коде, поэтому, если вы не знакомы с Java или не понимаете, что делает мой псевдо-код, сообщите мне. Во всяком случае, идея моего кода может представлять некоторые проблемы в зависимости от языка, с которым вы работаете, поэтому вам придется его адаптировать.

Обратите внимание, что в конце выполнения этой программы ваша структура данных не будет односвязным списком, а не двойной, так как у вас будут linkedList.length() - 1 узлы, соединенные знаковым образом, но средние будет иметь две ссылки.

Надеюсь, это поможет.

Answer 3

К определение, односвязный список состоит только из односвязных узлов, а двойная связь состоит только из узлов с двойной связью. В противном случае. это не так.

По определению , поле prev с двойным связанным списком сусла точки к предыдущему элементу.

Что бы вы ни построили. Это не так хорошо сказано.Так что, если вас действительно попросили в интервью (и не поняли вопроса - может быть, он хотел, чтобы вы указали, что ghis нарушает интерфейс?) Это случай для кода ужасных историй http://thedailywtf.com/ - раздел «некомпетентные интервьюеры ».