d)将崟链表按基准划分。以崟链表的首结点值x为基准将该崟链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前。数据结构代码
时间: 2024-10-09 19:05:55 浏览: 12
d) 将崟链表(这里可能是有序链表)按照基准值x分割成两部分通常涉及遍历链表并进行比较操作。以下是Python的一个简单示例,假设我们有一个单链表节点类`ListNode`:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_list(head, pivot_val):
if not head or not head.next:
return head
# 创建两个指针,一个用于较小元素,一个用于剩余元素
smaller_head = smaller_tail = ListNode(0)
larger_head = larger_tail = ListNode(0)
current = head
while current:
if current.val < pivot_val:
smaller_tail.next = current
smaller_tail = smaller_tail.next
else:
larger_tail.next = current
larger_tail = larger_tail.next
current = current.next
# 连接两个部分
smaller_tail.next = None
larger_head.next = head if pivot_val == head.val else None
return smaller_head.next if smaller_head.next else larger_head
# 示例
# 定义链表节点...
head = ... # 崎岖链表的头结点
pivot_val = head.val # 基准值,这里是头结点的值
new_head = split_list(head, pivot_val)
```
这个函数首先创建了两个空链表用于存储较小和较大的元素,然后遍历原链表,将元素分别添加到这两个新链表。最后返回较小元素链表的头结点,如果所有元素都等于基准值,则直接返回原始链表。