分離鏈接列表中的偶數和奇數節點

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只有next引用，而不是prev引用（帶有雙向引用的列表是稱爲雙向鏈表）。

even = even.next; 

由於even（和temp）都指向新創建Node目的，even.next屬性是null。所以當這條線執行時，even現在指向空。循環內的工作沒有成功，因爲您立即失去了對您創建的每個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; 
     }