Разделить четные и нечетные узлы в связанном списке

Question

Учитывая, связанный список, я пытаюсь разбить его так, чтобы четные узлы приходили к нечетным узлам. Мой подход заключается в создании двух разных связанных списков (четных и нечетных) для хранения четных чисел и нечетных чисел. Тем не менее, я столкнулся с проблемой, когда хочу добавить к четному или нечетному связанному списку (я прокомментировал часть, которая, как мне кажется, дает мне проблему в моем коде ниже). Благодаря!

public class SeperateOddEven { 

    static Node head; 
    static int count; 

    public static class Node { 
     int data; 
     Node next; 

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

    } 


    public void seperate() { 

     Node even = null; 
     Node odd = null; 
     Node temp; 

     // go through each linked-list and place node in new list depending on whether they are even or odd 
     while(head != null) { 
      // if even, place in even linked-list 
      if(head.data % 2 == 0) { 
       temp = new Node(head.data); 
       even = temp; // Problem here 
       even = even.next; // and here 
      } else { // if head.data % 2 != 0 
       temp = new Node(head.data); 
       odd = temp; 
       odd = odd.next; 
      } 
      head = head.next; 
     } 

     toString(even); 
     //toString(odd); 

    } 

    public void toString(Node node) { 
     while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
     } 
    } 

    public static void main(String[] args) { 

     SeperateOddEven s = new SeperateOddEven(); 
     head = new Node(8); 
     head.next = new Node(12); 
     head.next.next = new Node(10); 
     head.next.next.next = new Node(5); 
     head.next.next.next.next = new Node(4); 
     head.next.next.next.next.next = new Node(1); 
     head.next.next.next.next.next.next = new Node(6); 

     System.out.println("original list: "); 
     s.toString(head); 

     s.seperate(); 
    } 
} 

Answer 1

Я считаю, что вы точно определили, где проблема. Давайте построчно:

temp = new Node(head.data); 

Дополнительный temp переменная не нужна, но хорошо.

even = temp; 

Однако проблема возникает на следующей линии. Вы назначаете even на temp (что делает ненужный темп). Если что-то было ранее сохранено в even, оно теперь потеряно сборщику мусора, потому что теперь у вас нет ссылки на него. even и temp теперь являются ссылками на тот же объект Node.

Я думаю, что вы, возможно, хотели сделать, это сказать even.next = temp. Это начнет создавать список, но с единственной ссылкой вам придется использовать эту ссылку, чтобы указать на заголовок списка. Каждый раз, когда вы хотите добавить в список, вам нужно будет пропустить его, пока не найдете конец. Если вы попытаетесь сделать эту единственную контрольную точку в хвосте списка, у вас больше не будет возможности вернуться к голове, потому что ваши Node s имеют только ссылки next, а не prev ссылок (список с двунаправленными ссылками называемый дважды связанным списком).

even = even.next; 

Поскольку even (и temp) оба указывают на вновь созданную Node объекта, even.next свойство null. Поэтому, когда эта строка выполняется, even теперь указывает на null. Работа внутри цикла ничего не принесла, потому что вы сразу же теряете ссылки на каждый созданный вами Node.

попробовать что-то вроде этого:

// Must keep track of head reference, because your Nodes can only go forward 
Node evenHead = null; 
Node evenTail = null; 

Node oddHead = null; 
Node oddTail = null; 

while (head != null) { 
    if(head.data % 2 == 0) { 
     if (evenHead == null) { 
      // The even list is empty, set the head and tail 
      evenHead = new Node(head.data); 
      evenTail = evenHead; 
     } else { 
      // Append to the end of the even list 
      evenTail.next = new Node(head.data); 
      evenTail = evenTail.next; 
     } 
    } else { 
     // similar code for odd, consider creating a method to avoid repetition 
    } 
} 

Answer 2

Вы также можете попробовать это:

while (head != null) { 
      // if even, place in even linked-list 
      temp = new Node(head.data); 
      if (head.data % 2 == 0) { 
       if(even == null) { 
        even = temp; 
       } else{ 
        Node insertionNode = even; 
        while(insertionNode.next != null) 
         insertionNode = insertionNode.next; 
        insertionNode.next = temp; 
       } 


      } else { // if head.data % 2 != 0 
       if(odd == null) { 
        odd = temp; 
       } else{ 
        Node insertionNode = odd; 
        while(insertionNode.next != null) 
         insertionNode = insertionNode.next; 
        insertionNode.next = temp; 
       } 
      } 
      head = head.next; 
     }