给出一单链表L,分别编写程序,实现 1)将值为x的新节点插入p节点后面,并输出插入后的单链表; 在第i个节点前插入值为x的节点,并输出插入后的单链表;
时间: 2024-03-21 18:43:16 浏览: 56
我编写的实现单链表的程序
好的,我明白了。下面是对应的代码实现:
1)将值为x的新节点插入p节点后面,并输出插入后的单链表:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_after_node(head: ListNode, p: ListNode, x: int) -> ListNode:
if not head or not p:
return head
new_node = ListNode(x)
new_node.next = p.next
p.next = new_node
return head
```
2)在第i个节点前插入值为x的节点,并输出插入后的单链表:
```python
def insert_before_index(head: ListNode, i: int, x: int) -> ListNode:
if not head or i <= 0:
return head
if i == 1:
new_node = ListNode(x)
new_node.next = head
return new_node
cur_node = head
while i > 2 and cur_node:
cur_node = cur_node.next
i -= 1
if not cur_node:
return head
new_node = ListNode(x)
new_node.next = cur_node.next
cur_node.next = new_node
return head
```
需要注意的是,在第二个函数中,我们需要遍历链表找到第 i-1 个节点,然后在其后面插入新节点。如果 i=1,则需要特殊处理,直接将新节点插入到头部并返回。同时,如果 i 大于链表长度,则不进行任何操作,直接返回原链表。
阅读全文