删除单链表的交替部分，其中每个节点指向两个对象

Question

我正在使用带有段类型节点的单链表，每个段都指向一个位置和一种颜色。我的列表描述了一条毛毛虫，所以我不希望有任何不连续性 - 即，如果我删除 7 段毛毛虫的第二、第四和第六段，我希望第三段占据第二段的位置，第五段占据该位置第三个等，这样就不会有“洞”。但我当然希望新的第二部分保留第三部分的颜色。最后，我想将我不再使用的所有位置（例如第 5、6 和 7 段指向的最后 3 个位置）添加到名为 previousOccupiedPositions 的堆栈中。

这是我到目前为止的代码：

     // the caterpillar devours a slide of Swiss cheese, losing half of its segments.
     public void eat(SwissCheese cheese) {
        if (this.length <= 1) {
            return;
        }

        Stack<Position> positionsKept = new Stack<>();
        Stack<Position> positionsRemoved = new Stack<>();
        Segment temp = this.head;
        boolean removeSegment = false;
        while (temp != null) {
            if (!removeSegment) {
                positionsKept.push(temp.position);
            }
            else {
                positionsRemoved.push(temp.position);
            }

            removeSegment = !removeSegment;
            temp = temp.next;
        }

        this.length = (this.length +1)/2;

        this.head = new Segment(positionsKept.pop(), this.head.color);
        Segment curr = this.head;

        while (!positionsKept.isEmpty()) {
            curr.next = new Segment(positionsKept.pop(), curr.next.next.color);
            curr = curr.next;
        }

        while (!positionsRemoved.isEmpty()) {
            positionsPreviouslyOccupied.push(positionsRemoved.pop());
        }
    }

这有道理吗？我对最后一段代码特别有问题，我将 head 分配给 Segment 类型的新对象，然后再分配。

Answer 1

您有一个经典问题：从单链表中删除一个项目。这不取决于项目的数据。

您应该定义容器的类。以及内部项目表示（具有数据和对下一个节点的引用的节点）。最后实现删除方法。

如何从单链表中删除随机方法：

1. 找到该项目（例如

   A

   ）。
2. 查找上一项（例如

   preA

   ）
3. 查找下一个项目（例如

   nextA

   ）
4. 将参考从

   preA -> A

   更改为

   preA -> nextA

5. 删除参考

   A -> null

所以你的容器可能看起来像这样：

public final class SinglyLinkedList<T> {

    private Node<T> head;

    public void add(T data) {
        if (head == null)
            head = new Node<>(data);
        else {
            Node<T> node = head;

            while (node.next != null)
                node = node.next;

            node.next = new Node<>(data);
        }
    }

    @RequiredArgsConstructor
    private static final class Node<T> {

        private final T data;
        private Node<T> next;

    }

}

然后，例如如果你想删除每个

2nd

元素，那么它可能看起来像这样：

public List<T> removeEvenItems() {
    if (head == null || head.next == null)
        return List.of();

    boolean remove = false;
    Node<T> prv = null;
    Node<T> node = head;
    List<T> removed = new ArrayList<>();

    while (node != null) {
        if (remove) {
            removed.add(node.data);
            prv.next = node.next;
            node.next = null;
            node = prv.next;
        } else {
            prv = node;
            node = node.next;
        }

        remove = !remove;
    }

    return removed;
}

或者删除每个

1st

元素：

public List<T> removeOddItems() {
    if (head == null)
        return List.of();

    if (head.next == null) {
        T data = head.data;
        head = null;
        return List.of(data);
    }

    boolean remove = true;
    Node<T> prv = null;
    Node<T> node = head;
    List<T> removed = new ArrayList<>();

    while (node != null) {
        if (remove) {
            removed.add(node.data);

            if (prv == null) {
                head = node.next;
                node.next = null;
                node = head;
            } else {
                prv.next = node.next;
                node.next = null;
                node = prv.next;
            }
        } else {
            prv = node;
            node = node.next;
        }

        remove = !remove;
    }

    return removed;
}