现有一链表的头指针head,给定一个值x,编写一段代码将所有小于x的结点排在其余结点之前,且不改变原来的数据顺序,返回重新排列后的链表头指针。
时间: 2024-12-25 10:26:16 浏览: 13
为了实现这个功能,你可以采用双指针法,同时遍历链表。这里是一个简单的Python示例,假设链表节点有一个`val`属性存储数据,以及一个指向下一个节点的`next`属性:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def partitionList(head, x):
dummy = ListNode(0) # 创建虚拟头节点,用于连接两个部分
current = dummy # 初始化当前节点为dummy
smaller_head = None # 小于x的链表头节点
larger_head = head # 大于等于x的链表头节点
while larger_head is not None:
if larger_head.val < x: # 如果当前节点值小于x,将其添加到smaller_head部分
current.next = larger_head
current = current.next
else: # 否则,继续查找大于等于x的节点并添加到larger_head部分
if smaller_head is None: # 如果还没有创建smaller_head,设置它为当前节点
smaller_head = larger_head
current.next = None # 将较大节点直接接到dummy之后
current = larger_head # 移动current到下个节点
larger_head = larger_head.next # 更新较大的链表头节点
# 连接两个链表的结尾
current.next = larger_head # 小于x的链表末尾接上大于等于x的链表起始节点
return dummy.next # 返回新的链表头节点,即原来的smaler_head
```
阅读全文