提问人：Nitya Khirwar 提问时间：11/13/2023 更新时间：11/13/2023 访问量：40
删除单向链表的交替部分，其中每个节点指向两个对象
Removing alternate sections of a singly linked list where each node points to two objects
问：
我正在使用一个单向链表，其节点类型为 Segment，每个段都指向一个位置和颜色。我的列表描述了毛毛虫，所以我不希望有不连续性 - 即如果我删除 7 节毛毛虫的第 2、4 和 6 节，我希望第 3 节占据第 2 节的位置，第 5 节占据第 3 节的位置，依此类推，这样就没有“洞”。但是，当然，我希望新的第二段保留第三段的颜色。最后，我想将我不再使用的所有位置（例如第 5、6 和 7 段指向的最后 3 个位置）添加到名为 beforeOccupiedPositions 的堆栈中。
这是我到目前为止拥有的代码：
// 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 类型的新对象，然后再分配。
答：
0赞
Oleg Cherednik
11/13/2023
#1
您有一个经典的问题，即从单个链表中删除一个项目。这不取决于项目的数据。
您应该定义容器的类。和内部项目表示（具有数据和对下一个节点的引用的节点）。最后实现 delete 方法。
如何从单链表中删除随机方法：
- 找到项目（例如）。
A - 查找上一个项目（例如
preA) - 查找下一项（例如
nextA) - 将引用从 更改为
preA -> ApreA -> nextA - 删除引用
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;
}
评论