有头结点的单链表在P结点前插入S结点
时间: 2023-05-31 14:03:38 浏览: 59
假设有头结点的单链表如下:
```
head -> A -> B -> C -> P -> D -> E -> null
```
要在 P 结点前插入 S 结点,可以按照以下步骤进行:
1. 创建一个新结点 S,将其数据域设置为插入的数据。
2. 找到 P 结点的前一个结点,记为 prev。
3. 将 S 的 next 指针指向 P 结点。
4. 将 prev 的 next 指针指向 S。
具体实现可以参考下面的代码:
```java
public void insertBefore(Node p, Node s) {
Node prev = head;
while (prev.next != p && prev.next != null) {
prev = prev.next;
}
if (prev.next == p) {
s.next = p;
prev.next = s;
} else {
throw new IllegalArgumentException("p is not in the list.");
}
}
```
调用该方法可以在 P 结点前插入 S 结点:
```java
Node p = findNodeByValue("P");
Node s = new Node("S");
insertBefore(p, s);
```
插入后的链表如下:
```
head -> A -> B -> C -> S -> P -> D -> E -> null
```