分隔链表中的奇偶节点

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