java - 在java中交错两个节点列表

Question

我发布了一个类似的问题，但仍然遇到问题，尝试交错两个节点列表时遇到问题，根据我的测试用例，我应该得到 null，但它给出了一个包含“3D”的节点。

当我在 Eclipse 的 Debug模式下查看列表时，列表的持续时间似乎比应有的时间要长。测试了我的长度方法，它返回正确的长度。

我不明白为什么我的节点似乎会继续运行，而它应该只是下面发布的测试用例中的 13 个节点的列表。

代码应执行以下操作例如 {"KH","4C","8C","QC","3D","7D","JD"} 变为 {"KH","4C", "8C","QC"} {"3D","7D","JD"}(如果在本例中列表具有奇数个节点，则第一个列表更长)并返回列表 {"KH","3D","4C","7D","8C","JD","QC"}。

我必须使用提供的节点类来解决这个问题，并且不能使用静态变量、数组或 Java 集合。请不要只是发布代码，我真的需要学习如何操作节点，但不明白我所做的事情是错误的。

public class ListShuffleExample {

public static Node<String> shuffle(Node<String> deck) {
    if (deck == null) {
        return null;
    }
    if (deck.next == null) {
        return deck;
    }

    Node<String> lf = deck;
    int decklength = length(lf);
    int halflength;
    Node<String> first = deck;
    Node<String> second = deck;
    if (decklength % 2 == 0) {
        halflength = decklength / 2;

    } else {
        halflength = (decklength / 2) + 1;
    }

    for (int i = 0; i < halflength; i++) {
        second = second.next;
    }

    Node<String> curFirst = first;
    Node<String> curSecond = second;

    while (curFirst != null && curSecond != null) {
        // save the next one of the first list
        Node<String> nextFirst = curFirst.next;

        // set the next one of the first list to the first one of the second
        // list
        curFirst.next = curSecond;

        // save the next one of the second list
        Node<String> nextSecond = curSecond.next;

        // set the next one after the inserted item to the previous next of
        // the first list
        curSecond.next = nextFirst;

        // set the current references to the next ones
        curFirst = nextFirst;
        curSecond = nextSecond;
    }

    return first;
}

public static int length(Node<String> adeck) {
    int length = 0;

    while (adeck != null) {
        length++;
        adeck = adeck.next;
    }

    return length;
}
}

测试用例

import static org.junit.Assert.*;

import java.lang.reflect.Field;

import org.junit.Test;

public class ListShuffleExampleTest {
private static final Node<String> _AH = new Node<String>( "AH" );
private static final Node<String> _5H = new Node<String>( "5H" );
private static final Node<String> _9H = new Node<String>( "9H" );
private static final Node<String> _KH = new Node<String>( "KH" );
private static final Node<String> _4C = new Node<String>( "4C" );
private static final Node<String> _8C = new Node<String>( "8C" );
private static final Node<String> _QC = new Node<String>( "QC" );
private static final Node<String> _3D = new Node<String>( "3D" );
private static final Node<String> _7D = new Node<String>( "7D" );
private static final Node<String> _JD = new Node<String>( "JD" );
private static final Node<String> _2S = new Node<String>( "2S" );
private static final Node<String> _6S = new Node<String>( "6S" );
private static final Node<String> _TS = new Node<String>( "TS" );

private static <T> Node<T> makeList(Node<T>... nodes) {
    for (int i = 0; i < nodes.length-1; i++) {
        nodes[ i ].next = nodes[ i+1 ];
    }
    nodes[ nodes.length-1 ].next = null;
    return nodes[ 0 ];
}
@Test
public void testReflection() {
    Class<?> iClass  = ListShuffleExample.class;
    for (Field field : iClass.getDeclaredFields()) {
        if (!field.isSynthetic()) {
            fail( "class should not have any fields" );
        }
    }
}
@Test
public void testNull() {
    Node<String> actual = ListShuffleExample.shuffle( null );
    //expected: NULL
    assertEquals( "", null, actual );
}
@Test
public void testOddDivide10() {
    @SuppressWarnings("unchecked")
    Node<String> input  = makeList( _QC );
    Node<String> actual = ListShuffleExample.shuffle( input );
    for (Object expected : new Object[]{ _QC }) {
        assertEquals( "Incorrect value", expected, actual );
        actual = actual.next;
    }
    assertNull( "Incorrect result", actual );
}
@Test
public void testOddDivide21() {
    @SuppressWarnings("unchecked")
    Node<String> input  = makeList( _AH, _5H, _9H );
    Node<String> actual = ListShuffleExample.shuffle( input );
//                                           _AH,      _5H
//                                                _9H
    for (Object expected : new Object[]{ _AH, _9H, _5H }) {
        assertEquals( "Incorrect value", expected, actual );
        actual = actual.next;
    }
    assertNull( "Incorrect result", actual );
}
@Test
public void testEvenDivide22() {
    @SuppressWarnings("unchecked")
    Node<String> input  = makeList( _2S, _6S, _TS, _AH );
    Node<String> actual = ListShuffleExample.shuffle( input );
//                                           _2S,      _6S
//                                                _TS,      _AH
    for (Object expected : new Object[]{ _2S, _TS, _6S, _AH }) {
        assertEquals( "Incorrect value", expected, actual );
        actual = actual.next;
    }
    assertNull( "Incorrect result", actual );
}
@Test
public void testOddDivide43() {
    @SuppressWarnings("unchecked")
    Node<String> input  = makeList( _KH, _4C, _8C, _QC, _3D, _7D, _JD );
    Node<String> actual = ListShuffleExample.shuffle( input );
//                                           _KH,      _4C,      _8C,       _QC,
//                                                _3D,      _7D,      _JD
    for (Object expected : new Object[]{ _KH, _3D, _4C, _7D, _8C, _JD , _QC })   {
        assertEquals( "Incorrect value", expected, actual );
        actual = actual.next;
    }
    assertNull( "Incorrect result", actual );
}
@Test
public void testEvenDivide44() {
    @SuppressWarnings("unchecked")
    Node<String> input  = makeList( _5H, _9H, _KH, _4C, _8C, _QC, _3D, _7D );
    Node<String> actual = ListShuffleExample.shuffle( input );
//                                           _5H,      _9H,      _KH,      _4C,
//                                                _8C,      _QC,      _3D,      _7D
    for (Object expected : new Object[]{ _5H, _8C, _9H, _QC, _KH, _3D, _4C, _7D   }) {
        assertEquals( "Incorrect value", expected, actual );
        actual = actual.next;
    }
    assertNull( "Incorrect result", actual );
}
@Test
public void testMany() {
    @SuppressWarnings("unchecked")
    Node<String> input  = makeList( _AH, _5H, _9H, _KH, _4C, _8C, _QC, _3D, _7D, _JD, _2S, _6S, _TS );
    Node<String> actual = ListShuffleExample.shuffle( input );
//                                           _AH,      _5H,      _9H,      _KH,      _4C,      _8C,      _QC
//                                                _3D,      _7D,      _JD,      _2S,      _6S,      _TS
    for (Object expected : new Object[]{ _AH, _3D, _5H, _7D, _9H, _JD, _KH, _2S, _4C, _6S, _8C, _TS, _QC }) {
        assertEquals( "Incorrect value", expected, actual );
        actual = actual.next;
    }
    assertNull( "Incorrect result", actual );
}
}

节点类

public final class Node<T> {
public final T       value;
public       Node<T> next;

public Node(T _value) {
    this( _value, null );
}
public Node(T _value, Node<T> _next) {
    value = _value;
    next  = _next;
}
@Override
public String toString() {
    return "" + value;
}
}

Answer 1

您似乎忘记取消第一个列表末尾与第二个列表开头的链接。

您希望列表的末尾指向 null，但您却留下了一个返回到第二个列表的原始开头的链接。当您有偶数分区时，它会起作用，因为最后一个元素已经 null 终止。但是，当您有奇数分区时，您需要考虑额外的元素。

编辑:循环可以通过两个条件的组合终止:curFirst == null 或 curSecond == null 或两者兼而有之。您应该考虑是什么导致循环终止，以及哪些条件必须为真。另外，考虑是否还有剩余元素。

(您特意要求我们不要发布代码!)