编写一个程序使用单链表 将单链表按基准划分,以单链表的首节点值x为基准将该单链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前。
时间: 2024-10-07 17:07:28 浏览: 43
c代码-编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可,其不需要被置于左右两部分之间。
在编写一个程序来按基准划分单链表时,首先需要定义链表节点结构,并创建两个新的链表头指针,分别用于存储小于基准值和大于等于基准值的元素。以下是一个基本的步骤:
1. 定义链表节点结构(例如在Python中):
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```
2. 创建函数来遍历链表并分割它:
```python
def partition_list(head, x):
if not head or not head.next:
return head
# 创建两个指向当前元素的指针和基准指针
less_than_x = ListNode(0)
equal_or_greater_than_x = ListNode(0)
less_than_x_head = less_than_x
greater_head = equal_or_greater_than_x
current = head
while current:
if current.val < x:
less_than_x.next = current
less_than_x = less_than_x.next
else:
greater_head.next = current
greater_head = greater_head.next
current = current.next
# 连接两个链表的尾巴
greater_head.next = None
less_than_x.next = greater_head.next
return less_than_x_head.next
```
这个函数首先初始化了两个空链表 `less_than_x` 和 `equal_or_greater_than_x`,然后遍历输入链表,根据每个节点值与基准值的关系将其添加到相应的链表中。最后,连接两个链表并返回结果。
阅读全文