在链表中插入元素通常涉及以下步骤:
找到插入位置的前一个节点:
这是因为在链表中插入一个新节点需要将新节点链接到前一个节点后面。
创建新节点:
将要插入的值赋给新节点,并初始化其`next`指针为`null`。
调整指针:
将新节点的`next`指针指向插入位置的节点,并将前一个节点的`next`指针指向新节点。
特殊情况
在链表头部插入:此时没有前一个节点,直接将新节点的`next`指针指向头节点,并更新头节点为新节点。
在链表尾部插入:需要遍历到链表的最后一个节点,然后在其后插入新节点。
代码示例
```java
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
private ListNode head;
public LinkedList() {
head = null;
}
// 在链表头部插入元素
public void addFirst(int val) {
ListNode newNode = new ListNode(val);
newNode.next = head;
head = newNode;
}
// 在链表尾部插入元素
public void addLast(int val) {
ListNode newNode = new ListNode(val);
if (head == null) {
head = newNode;
} else {
ListNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// 在指定位置插入元素
public void insert(int index, int val) {
if (index == 0) {
addFirst(val);
return;
}
ListNode newNode = new ListNode(val);
ListNode previous = null;
ListNode current = head;
for (int i = 0; i < index - 1 && current != null; i++) {
previous = current;
current = current.next;
}
if (current == null) {
addLast(val);
} else {
newNode.next = current;
previous.next = newNode;
}
}
// 打印链表
public void printList() {
ListNode current = head;
while (current != null) {
System.out.print(current.val + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(0);
list.addLast(3);
list.addLast(4);
list.insert(3, 5);
list.printList(); // 输出: 0 -> 1 -> 2 -> 5 -> 3 -> 4 -> null
}
}
```
总结
链表插入元素的关键在于找到插入位置的前一个节点,并正确调整指针。在特殊情况下,如链表头部或尾部插入,需要做一些额外的处理。以上代码示例展示了如何在Java中实现这些操作。