有一个整数单链表L,设计一个算法在第i个结点之前插入一个元素x,若参数错误返回false,否则插入后返回true。例如,L=(1,2,3,4,5),i=0,x=6,插入后 L=(6,1,2,3,4,5)。用Java代码实现
时间: 2024-10-14 16:10:44 浏览: 26
在Java中,你可以通过遍历链表并在找到第i个节点的位置插入新节点来实现这个功能。如果链表长度小于i或者i超出范围,则返回false。下面是一个简单的Java函数实现:
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public boolean insertBefore(ListNode head, int i, int x) {
if (head == null || i <= 0) return false; // 检查输入是否合法
ListNode dummy = new ListNode(0); // 创建哑节点作为头节点,方便处理头节点的插入
dummy.next = head;
int count = 1; // 记录当前遍历到的节点
ListNode prev = dummy; // 上一个节点指针初始化为哑节点
ListNode curr = head; // 当前节点指针初始化为头节点
while (curr != null && count < i) {
prev = curr;
curr = curr.next;
count++;
}
if (curr == null) return false; // 如果i超过链表长度,未到达目标位置,返回false
prev.next = new ListNode(x); // 插入新节点
prev.next.next = curr; // 将原节点移到新节点之后
return true;
}
}
```
在这个代码里,我们首先检查了基本情况,然后创建了一个哑节点,并设置它作为新的头节点。接着遍历链表,直到找到第i个节点或达到链表末尾。一旦找到了目标位置,就在该节点之前插入新节点,并调整后续节点的引用。
阅读全文