隔离链表中的偶数节点和奇数节点

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现在指向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;
        }