编写一个程序,以给定值x为基准将单链表分割为两部分,所有小于x的节点排在大于或等于x的节点之前。
时间: 2024-10-14 12:13:45 浏览: 36
要编写一个程序来分割单链表,首先需要定义链表结构以及遍历链表的基本操作。假设我们有一个链表节点的定义如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```
然后我们可以创建一个函数`split_list`来完成这个任务:
```python
def split_list(head, x):
if not head or not head.next:
# 如果链表为空或只有一个元素
return head
smaller_head = ListNode(0) # 新链表用于存储小于x的节点
smaller_head.next = head
larger_head = ListNode(0) # 新链表用于存储大于等于x的节点
current = head
while current is not None:
if current.val < x:
smaller_head = smaller_head.next
else:
larger_head.next = current
larger_head = larger_head.next
current = current.next
# 结束后,larger_head.next 就会是 None,因为最后一个大于等于x的节点之后没有更多的节点了
return smaller_head.next if smaller_head.next != larger_head else larger_head
```
这个函数的工作原理是遍历原始链表,每次遇到小于x的节点就将其添加到较小链表中,遇到大于等于x的节点则添加到较大链表,并更新较大链表的头节点。
阅读全文