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

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 (使 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 
    }
}