现有一链表的头指针 ListNode " pHead ,给一定值 x ,编写一段代码将所有小于 x 的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
时间: 2024-12-20 16:20:36 浏览: 3
这是一个典型的链表操作问题,可以使用两个指针和分治的思想来解决。首先创建一个新的链表,遍历原链表 `pHead`,对于每个节点 `node`:
1. 如果 `node` 的值小于 `x`,则在新链表头部插入这个节点。
2. 否则,在新链表剩余部分添加 `node`。
遍历完成后,新链表的头部就是结果。由于只对节点进行了移动,并未修改节点的实际值,所以原链表数据的顺序保持不变。以下是伪代码描述:
```python
def reorderList(pHead, x):
dummy = ListNode(0) # 创建虚拟头节点,用于连接新旧链表
new_head = dummy
less_head = dummy
while pHead is not None:
if pHead.val < x: # 小于 x 的节点添加到新链表头部
less_head.next = pHead
less_head = less_head.next
else: # 不小于 x 的节点添加到新链表剩余部分
pHead.next = new_head.next
new_head.next = pHead
pHead = pHead.next
less_head.next = None # 新链表结束,将其连接到旧链表的尾部
return dummy.next # 返回新链表的头节点
```
阅读全文