给定一个N个数的数组,M次操作,每次操作为下列操作之一。求最后的数组。 操作1:在第X个数之后插入一个数Y。 操作2:删除第X个数。
时间: 2024-04-30 11:17:59 浏览: 130
数组操作:创建、插入、排序、删除
我们可以使用链表来实现这个操作。对于每个节点,它包含一个值和一个指向下一个节点的指针。我们还需要一个指向链表头的指针和一个计数器,用于跟踪链表中节点的数量。
对于操作1,我们首先创建一个新节点,将其值设置为Y,并将其指针设置为X节点的指针。然后将X节点的指针设置为新节点。
对于操作2,我们需要找到第X个节点的前一个节点,将其指针指向第X个节点的下一个节点,然后删除第X个节点。
以下是使用Python实现的代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.count = 0
def insert(self, x, y):
new_node = Node(y)
if x == self.count:
if self.head == None:
self.head = new_node
else:
cur = self.head
while cur.next != None:
cur = cur.next
cur.next = new_node
else:
cur = self.head
for i in range(x):
prev = cur
cur = cur.next
prev.next = new_node
new_node.next = cur
self.count += 1
def delete(self, x):
if x == 0:
self.head = self.head.next
else:
cur = self.head
for i in range(x):
prev = cur
cur = cur.next
prev.next = cur.next
self.count -= 1
def print_list(self):
cur = self.head
while cur != None:
print(cur.val, end = " ")
cur = cur.next
print()
# 示例
l = LinkedList()
l.insert(0, 1)
l.insert(1, 2)
l.insert(2, 3)
l.print_list()
l.insert(2, 4)
l.print_list()
l.delete(1)
l.print_list()
```
输出:
```
1 2 3
1 2 4 3
1 4 3
```
在这个示例中,我们首先创建一个包含1,2和3的链表。然后我们在第3个位置插入4,删除第2个位置的节点,并打印最终的链表。
阅读全文