Segregate gerade und ungerade Knoten in einer verknüpften Liste

Question

Gegeben, eine verknüpfte Liste, ich versuche es zu partitionieren, so dass die geraden Knoten vor den ungeraden Knoten kommen. Mein Ansatz besteht darin, zwei verschiedene verknüpfte Listen (gerade und ungerade) zu erstellen, um gerade Zahlen und ungerade Zahlen zu speichern. Allerdings stoße ich auf ein Problem, wenn ich zur geraden oder ungeraden verknüpften Liste hinzufügen möchte (ich habe den Teil kommentiert, von dem ich glaube, dass er mir in meinem Code Probleme gibt). Vielen Dank!

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

Ich glaube, Sie identifiziert genau, wo das Problem liegt. Lassen Sie sich Zeile für Zeile gehen:

temp = new Node(head.data); 

Das zusätzliche temp variable unnötig, aber fein ist.

Ein Problem entsteht jedoch in der nächsten Zeile. Sie weisen even zu temp zu (das macht die Temperatur unnötig). Wenn zuvor etwas in even gespeichert wurde, ist es jetzt für den Garbage Collector verloren, weil Sie jetzt keinen Verweis darauf haben. even und temp sind nun beide Referenzen auf das gleiche Node Objekt.

Was ich denke, dass Sie vielleicht wollten, war zu sagen even.next = temp. Dies würde beginnen, eine Liste zu erstellen, aber mit nur einer einzigen Referenz müssten Sie diese Referenz verwenden, um auf den Kopf der Liste zu zeigen. Jedes Mal, wenn Sie an die Liste anhängen möchten, müssen Sie die Schleife durchlaufen, bis Sie das Ende gefunden haben. Wenn Sie stattdessen versuchen, diesen einzelnen Referenzpunkt zum Ende der Liste zu machen, hätten Sie keine Möglichkeit mehr, zum Kopf zurückzukehren, da Ihre Node s nur next Referenzen und nicht prev Referenzen (eine Liste mit bidirektionalen Referenzen) hat eine doppelt verknüpfte Liste genannt).

even = even.next; 

Da even (und temp) beide auf den neu erstellten Node Objekt, das even.next Eigenschaft ist null. Wenn diese Zeile ausgeführt wird, zeigt even jetzt auf null. Die Arbeit innerhalb der Schleife hat nichts bewirkt, weil Sie sofort Referenzen auf alle Node verlieren, die Sie erstellen.

versuchen, etwas wie folgt aus:

// 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

Sie können auch versuchen, diese:

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