Bağlantılı bir Listedeki eşit ve tek düğümleri ayırma

Question

Bağlantılı bir liste verildiğinde, çift düğümlerin tek düğümlerden önce gelmesi için onu bölümlemeye çalışıyorum. Benim yaklaşımım, sayıları ve tek sayıları bile saklamak için iki farklı bağlantılı liste (çift ve tek) oluşturmaktır. Ancak, tek veya tek bağlantılı bir listeye eklemek istediğimde bir sorunla karşılaşıyorum (bana aşağıdaki kodumda sorun olduğunu düşündüğüm kısmı yorumladım). Teşekkürler!

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

Sorunun tam olarak nerede olduğunu belirlediğinize inanıyorum. satır satır dönelim:

temp = new Node(head.data); 

ekstra temp değişken gereksiz ama gayet iyi. Bununla birlikte, bir sonraki satırda bir sorun ortaya çıkmaktadır. even'u temp'a atayabilirsiniz (temp gereksiz). Bir şey daha önce even'da saklandıysa, artık çöp toplayıcısına kaybolur, çünkü artık referansınız yok. even ve temp artık ikisi de aynı Node nesnesine başvuruyor.

Yapmak isteyebileceğinizi düşündüğüm şey, even.next = temp demek idi. Bu bir liste oluşturmaya başlayacaktı, ancak sadece tek bir referansla bu referansı listenin başına yönlendirmek için kullanmanız gerekecekti. Listeye eklemek istediğiniz her seferinde, son noktayı bulana kadar döngü içinde olmanız gerekir. Bunun yerine, bu tek referans noktasını listenin kuyruğuna getirmeyi denediyseniz, artık Node s yalnızca next başvurusuna sahip olmanız ve prev başvurularından değil (çift yönlü referanslar içeren bir listeden) geri dönmeniz için herhangi bir yolunuz olmayacaktı. çift ​​bağlantılı bir liste denir).

even = even.next; 

even (ve temp) yeni oluşturulan Node nesneye her iki nokta, even.next özelliği null olduğu için. Bu satır yürütüldüğünde, even şimdi null değerini gösterir. Döngü içindeki iş hiçbir şey başarmadı, çünkü oluşturduğunuz her Node referansı hemen kaybedersiniz. Böyle

deneyin şey:

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

Ayrıca bu deneyebilirsiniz:

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