Java实现两个循环单链表有序并集输出元素冗余问题求助

核心问题原因 #

• 遍历终止条件错误导致链表循环绕圈，重复插入元素：
  原来的代码使用cur != rear作为循环终止条件，当指针移动到rear节点后，执行cur = cur.next会回到链表头节点，此时cur != rear恒成立，会持续遍历插入整个链表的元素，这是输出元素数量远大于输入总和的直接原因。
  同时cur != rear的判断会漏掉rear节点本身的元素处理，进一步导致逻辑混乱。
• 归并逻辑的前置条件不满足：
  你使用的两路归并逻辑，要求两个输入链表本身是升序有序的，但你当前的insert方法是普通尾插，输入的两个链表都是乱序状态，即使修复遍历问题，输出结果也不会有序。
• 剩余元素处理逻辑冗余且错误：
  第一个循环退出后，你直接写了两个剩余元素遍历的do-while循环，哪怕对应链表已经遍历完毕也会执行，进一步触发绕圈问题。

修复方案 #

第一步：修复union方法的遍历逻辑 #

正确遍历循环单链表的判断条件是指针回到头节点，修改后的代码如下，可首先解决元素重复插入的问题：

public CircularLinkedList union(CircularLinkedList a, CircularLinkedList b) {
    CircularLinkedList c = new CircularLinkedList();
    // 处理空链表边界情况
    if (a.isEmpty()) {
        Element curB = b.head;
        do {
            c.insert(curB.data);
            curB = curB.next;
        } while (curB != b.head);
        return c;
    }
    if (b.isEmpty()) {
        Element curA = a.head;
        do {
            c.insert(curA.data);
            curA = curA.next;
        } while (curA != a.head);
        return c;
    }

    Element curA = a.head;
    Element curB = b.head;
    boolean aFinish = false, bFinish = false;

    // 归并逻辑，要求a、b本身为升序
    while (!aFinish && !bFinish) {
        if (curA.data < curB.data) {
            c.insert(curA.data);
            curA = curA.next;
            if (curA == a.head) aFinish = true;
        } else {
            c.insert(curB.data);
            curB = curB.next;
            if (curB == b.head) bFinish = true;
        }
    }

    // 插入a的剩余元素
    while (!aFinish) {
        c.insert(curA.data);
        curA = curA.next;
        if (curA == a.head) aFinish = true;
    }

    // 插入b的剩余元素
    while (!bFinish) {
        c.insert(curB.data);
        curB = curB.next;
        if (curB == b.head) bFinish = true;
    }

    // 若需要并集去重，可在插入时调用isInList方法判断元素是否已存在
    return c;
}

第二步：实现有序并集（可选，按需选择） #

两路归并逻辑要求输入链表本身是升序状态，你可以新增有序插入方法，保证插入元素后链表始终有序，示例代码如下：

// 升序有序插入方法
public void sortedInsert(int value) {
    Element tmp = new Element(value);
    if (this.head == null) {
        tmp.next = tmp;
        this.head = tmp;
        this.rear = tmp;
        return;
    }
    Element cur = head, prev = rear;
    // 找到第一个大于等于value的节点位置
    while (cur != rear && cur.data < value) {
        prev = cur;
        cur = cur.next;
    }
    // 插入到尾节点之后的情况
    if (cur == rear && cur.data < value) {
        tmp.next = head;
        rear.next = tmp;
        this.rear = tmp;
        return;
    }
    // 普通位置插入
    prev.next = tmp;
    tmp.next = cur;
    // 插入到头部的情况，更新头节点
    if (cur == head) {
        this.head = tmp;
    }
}

将main方法中的insert调用替换为sortedInsert，配合上面修改后的union方法，即可得到有序的并集输出结果。

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