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

kb5ga3dv 于 12个月前发布在 Java

关注(0)|答案(1)|浏览(109)

我使用的是一个单链表，其中节点类型为Segment，每个segment都指向一个位置和一种颜色。我的列表描述了一个毛毛虫，所以我不希望有不连续性-即如果我删除一个7段毛毛虫的第2、第4和第6段，我希望第3段占据第2段的位置，第5段占据第3段的位置，但是我当然希望新的第二段保留第三段的颜色。最后，我想把所有我不再使用的位置--比如第五、第六和第七段指向的最后三个位置--添加到我的堆栈中，称为previouslyOccupiedPositions。
以下是我目前为止的代码：

// 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类型的对象，然后。

Java

来源：https://stackoverflow.com/questions/77470730/removing-alternate-sections-of-a-singly-linked-list-where-each-node-points-to-tw

1条答案

按热度按时间

pkmbmrz71#

你有一个经典的问题，从单链表中删除一个项目。这不依赖于项目的数据。
你应该定义一个容器的类。和内部项表示（一个节点的数据和对下一个节点的引用）。最后实现删除方法。
如何从单链表中删除randome方法：
1.找到项目（例如A）。
1.查找前一项（例如preA）
1.查找下一个项目（例如nextA）
1.将引用从preA -> A更改为preA -> nextA
1.删除参考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;
}

型

赞(0）回复(0）举报 12个月前

我来回答

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

1条答案

相关问题

热门标签

最新问答