双向链表合并函数首while循环未执行及遍历疑问排查

Let's break down your two questions and fix the merge logic to align with your requirements, step by step.

Why isn't the first while loop executing? #

The first loop uses the condition curr1 != null && curr2 != null—so it won't run if either:

• list1 is empty (so getFirst() returns null), or
• list2 is empty (so getLast() returns null), or
• There's a bug in your DLL class's getLast() method (it returns null even when list2 has elements, usually because the tail pointer wasn't updated correctly when adding nodes).

To quickly diagnose, add debug prints right before the first loop:

System.out.println("curr1 exists? " + (curr1 != null));
System.out.println("curr2 exists? " + (curr2 != null));

This will tell you exactly which node reference is null blocking the loop.

Why is your traversal/merge logic not working as expected? #

Your current code doesn't follow the specified merge rules at all, which is why your output doesn't match the example. Let's recap the rules and fix the code:

The Required Merge Rules Recap #

1. Alternate adding even numbers: list1 from head, list2 from tail (your example shows 10 (list2 tail even) → 2 (list1 head even) → 8 (list2 previous even) → 4 (list1 next even), etc.)
2. Add remaining evens from list1
3. Add remaining evens from list2
4. Add all odds from list1 (head to tail)
5. Add all odds from list2 (tail to head)

Key Issues in Your Original Code #

• You're adding all list1 evens first, then all list2 evens—no alternation as required.
• You move pointers regardless of whether you found an even, which skips nodes incorrectly.
• Typo in the last loop: lista.insertLast() instead of list3.insertLast() (this would cause a compile error).

Fixed Merge Code #

public static void merge(DLL<Integer> list1, DLL<Integer> list2, DLL<Integer> list3) {
    DLLNode<Integer> curr1 = list1.getFirst();
    DLLNode<Integer> curr2 = list2.getLast();
    
    // Rule 1: Alternate evens (list2 tail → list1 head, repeat)
    boolean foundEven1, foundEven2;
    do {
        foundEven1 = false;
        foundEven2 = false;
        
        // First, find next even in list2 (moving backward)
        while (curr2 != null && curr2.element % 2 != 0) {
            curr2 = curr2.pred;
        }
        if (curr2 != null) {
            list3.insertLast(curr2.element);
            curr2 = curr2.pred;
            foundEven2 = true;
        }
        
        // Then, find next even in list1 (moving forward)
        while (curr1 != null && curr1.element % 2 != 0) {
            curr1 = curr1.succ;
        }
        if (curr1 != null) {
            list3.insertLast(curr1.element);
            curr1 = curr1.succ;
            foundEven1 = true;
        }
    } while (foundEven1 || foundEven2);
    
    // Rule 2: Add remaining evens from list1
    while (curr1 != null) {
        if (curr1.element % 2 == 0) {
            list3.insertLast(curr1.element);
        }
        curr1 = curr1.succ;
    }
    
    // Rule 3: Add remaining evens from list2
    while (curr2 != null) {
        if (curr2.element % 2 == 0) {
            list3.insertLast(curr2.element);
        }
        curr2 = curr2.pred;
    }
    
    // Rule 4: Add all odds from list1 (head to tail)
    curr1 = list1.getFirst();
    while (curr1 != null) {
        if (curr1.element % 2 != 0) {
            list3.insertLast(curr1.element);
        }
        curr1 = curr1.succ;
    }
    
    // Rule 5: Add all odds from list2 (tail to head)
    curr2 = list2.getLast();
    while (curr2 != null) {
        if (curr2.element % 2 != 0) {
            list3.insertLast(curr2.element); // Fixed typo here
        }
        curr2 = curr2.pred;
    }
}

How This Fixed Code Works #

• For Rule 1: We loop until no more evens are found in either list. We first grab the next even from list2 (moving backward), then the next even from list1 (moving forward)—matching your example's order perfectly.
• Rules 2-3: Continue traversing from where we left off in Rule 1 to collect any remaining evens.
• Rules 4-5: Traverse list1 from head to tail for odds, list2 from tail to head for odds—exactly as required.

内容的提问来源于stack exchange，提问作者Hana Kim