建立一个长度为n的单链表。 (2) 删除单链表中元素值最小的结点(假设这样的结点唯一)。(3) 删除单链表中元素值最大的结点(假设这样的结点唯一)。 I
时间: 2024-10-08 12:18:55 浏览: 20
建立一个长度为 n 的单链表通常涉及以下几个步骤:
1. 创建头节点 (head) 和空列表:首先,你需要创建一个 `ListNode` 类表示链表节点,包含一个整数值和指向下一个节点的引用。然后,你可以初始化一个头节点 `head`,其 next 指针设为 `None` 表示初始的链表为空。
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 初始化一个长度为 n 的链表
def create_list(n):
if n == 0:
return None
head = ListNode(n)
for _ in range(1, n):
head.next = ListNode(_)
head = head.next
return head
```
删除元素值最小的结点:
(2) 对于查找并删除最小值的操作,可以遍历整个链表,在找到第一个节点的同时也记录当前最小值。如果遇到更小的值,则更新最小值和对应的节点。删除操作是在找到最小值节点之后,将它的前一个节点的 next 指向它后面的节点。
```python
def delete_min(head):
if not head or not head.next:
return head
current = min_val = head
while current.next:
if current.next.val < min_val.val:
min_val = current.next
current = current.next
if min_val is not head:
current.next = current.next.next
else:
head = head.next
return head
```
删除元素值最大的结点:
(3) 同样地,遍历链表找出最大值,并在其后断开连接。这里需要注意,当链表只有一个节点或者所有节点值都相同时,需要特殊处理防止出现错误。
```python
def delete_max(head):
if not head or not head.next:
return head
max_val = current = head
while current.next:
if current.next.val > max_val.val:
max_val = current.next
current = current.next
if max_val is not head:
current.next = current.next.next
else:
# 如果链表只有一个元素或全为最大值,返回 None
if not current.next:
return None
head = head.next
return head
```
阅读全文