如何按指定交错规则合并两个IntList类型的Java单向链表？

现有代码的问题 #

你写的递归逻辑存在明显缺陷：每次调用merge(Q.rest, S)时，直接跳过了当前Q节点的first值，导致Q链表的奇数位元素全部丢失，最终输出结果自然不符合预期。

合并规则确认 #

根据你给出的示例推导，合并规则为：

• 按顺序优先从S取1个元素，之后连续从Q取2个元素
• 循环执行上述操作，直到某一个链表剩余元素不足
• 最后将未遍历完的链表的所有剩余元素直接追加到结果末尾

正确实现代码 #

递归实现版本 #

public static IntList merge(IntList S, IntList Q) {
    if (S == null) {
        return Q;
    }
    if (Q == null) {
        return S;
    }
    // 先取S的第一个元素
    IntList current = new IntList(S.first, null);
    IntList tail = current;
    // 取Q的第一个元素
    tail.rest = new IntList(Q.first, null);
    tail = tail.rest;
    // 尝试取Q的第二个元素，如果存在的话
    if (Q.rest != null) {
        tail.rest = new IntList(Q.rest.first, null);
        tail = tail.rest;
        // 递归处理剩下的S.rest和Q.rest.rest
        tail.rest = merge(S.rest, Q.rest.rest);
    } else {
        // Q只剩一个元素，剩下的直接接S的剩余部分
        tail.rest = S.rest;
    }
    return current;
}

迭代实现版本（无栈溢出风险，更易调试） #

public static IntList merge(IntList S, IntList Q) {
    if (S == null) return Q;
    if (Q == null) return S;

    // 虚拟头节点，简化边界处理
    IntList dummy = new IntList();
    IntList tail = dummy;
    IntList pS = S;
    IntList pQ = Q;

    while (pS != null && pQ != null) {
        // 取S的一个节点
        tail.rest = new IntList(pS.first, null);
        tail = tail.rest;
        pS = pS.rest;

        // 取Q的第一个节点
        tail.rest = new IntList(pQ.first, null);
        tail = tail.rest;
        pQ = pQ.rest;

        // 取Q的第二个节点（如果存在）
        if (pQ != null) {
            tail.rest = new IntList(pQ.first, null);
            tail = tail.rest;
            pQ = pQ.rest;
        }
    }

    // 追加剩余元素
    if (pS != null) {
        tail.rest = pS;
    }
    if (pQ != null) {
        tail.rest = pQ;
    }

    return dummy.rest;
}

验证测试 #

用你给出的示例测试：

• S = IntList.of(1,9,5,3)
• Q = IntList.of(0,4,3,6,6,2)
• 调用merge方法后输出的结果和你给出的预期结果[1,0,4,9,5,3,6,3,6,2]完全一致。

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