如何将现有节点添加至链表头部？递归拆分奇偶链表遇.add(IntNode)异常求助

Hey Jordan, let's tackle this linked list split issue together! It sounds like your .add(IntNode) method is causing unexpected overwrites, which is messing up the alternation of your odd and even lists. Let's break down what might be going wrong and fix it step by step.

First, Let's Diagnose the .add Method Issue #

The most likely culprit here is how your .add method is implemented. If it's not properly traversing to the tail of the target list before appending the new node, it'll overwrite existing nodes instead of extending the list. For example, a broken add might look like this (it just replaces the head or links incorrectly):

// Bad implementation that causes overwrites
public void add(IntNode newNode) {
    this.head = newNode;
    newNode.next = this.head; // Creates a loop or wipes prior nodes
}

We'll fix this first with a proper tail-based add method.

Revised Recursive Split Logic #

The key for recursive splitting is to:

1. Handle the base case (empty list)
2. Recursively process the rest of the list first
3. Append the current node to either the odd or even list (using a correct add method)
4. Finally, clear the original list

Here's a complete, corrected implementation (assuming your IntNode class has data and next fields):

class IntNode {
    int data;
    IntNode next;
    IntNode(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListSplitter {
    // Helper: Safely add a node to the TAIL of a list (fixes your overwrite issue)
    private void addToTail(IntNode listHead, IntNode newNode) {
        if (listHead == null) {
            listHead = newNode;
            return;
        }
        IntNode current = listHead;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.next = null; // Ensure no leftover links
    }

    // Recursive method to split into odd/even lists
    // Returns an array where index 0 = odd list head, index 1 = even list head
    private IntNode[] splitOddEvenRecursive(IntNode current) {
        // Base case: no more nodes to process
        if (current == null) {
            return new IntNode[]{null, null};
        }

        // First process the rest of the list recursively
        IntNode[] splitResult = splitOddEvenRecursive(current.next);
        IntNode oddHead = splitResult[0];
        IntNode evenHead = splitResult[1];

        // Append current node to the correct list
        if (current.data % 2 == 1) {
            if (oddHead == null) {
                oddHead = current;
            } else {
                addToTail(oddHead, current);
            }
        } else {
            if (evenHead == null) {
                evenHead = current;
            } else {
                addToTail(evenHead, current);
            }
        }

        return new IntNode[]{oddHead, evenHead};
    }

    // Public method to trigger split and clear original list
    public void splitAndClear(IntNode originalHead) {
        IntNode[] splitLists = splitOddEvenRecursive(originalHead);
        IntNode oddList = splitLists[0];
        IntNode evenList = splitLists[1];

        // Clear the original list by nulling its head
        originalHead = null;

        // Use oddList and evenList as needed (e.g., print them)
        printList("Odd List:", oddList);
        printList("Even List:", evenList);
    }

    // Helper to print lists for testing
    private void printList(String label, IntNode head) {
        System.out.print(label + " ");
        IntNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

Key Fixes Explained #

1. addToTail Method: This ensures new nodes are appended to the end of the target list, not overwriting existing nodes.
2. Recursive Flow: By processing the rest of the list first, we build the odd/even lists in the same order as the original list.
3. Clearing the Original List: Setting originalHead = null breaks all references to the original list nodes (assuming no other references exist).

内容的提问来源于stack exchange，提问作者Jordan Portz