头歌数据结构与算法单链表插入
时间: 2023-09-30 10:11:08 浏览: 78
对于单链表的插入操作,有两种常见的情况:在链表的头部插入一个新节点和在链表的指定位置插入一个新节点。
1. 在链表头部插入新节点:
首先,创建一个新的节点,并将新节点的值设为待插入的值。
然后,将链表的头节点作为新节点的下一个节点。
最后,将新节点设为链表的新头节点。
2. 在链表指定位置插入新节点:
首先,遍历链表找到待插入位置的前一个节点。
然后,创建一个新的节点,并将新节点的值设为待插入的值。
接下来,将原来前一个节点的下一个节点设为新节点的下一个节点。
最后,将新节点设为原来前一个节点的下一个节点。
具体实现代码如下(使用Python语言):
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insertAtHead(head, value):
new_node = ListNode(value)
new_node.next = head
return new_node
def insertAtPosition(head, position, value):
if position == 0:
return insertAtHead(head, value)
cur = head
for _ in range(position-1):
if cur.next is None:
raise ValueError("Invalid position")
cur = cur.next
new_node = ListNode(value)
new_node.next = cur.next
cur.next = new_node
return head
```
使用示例:
```python
# 创建一个链表 1 -> 2 -> 4
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(4)
# 在头部插入新节点 0
head = insertAtHead(head, 0)
# 在位置 2 插入新节点 3
head = insertAtPosition(head, 2, 3)
```
以上是单链表插入操作的基本思路和实现代码。在实际使用中,可以根据具体需求进行相应的修改和优化。