当前位置： 面试刷题>> 分隔链表(经典算法150题)
### 题目描述
**分隔链表**：给定一个链表和一个特定值 `x`，将链表分为两个部分，所有小于 `x` 的节点放在所有大于或等于 `x` 的节点之前，并且保持原有的相对顺序。
**示例**：
假设链表为 `1 -> 4 -> 3 -> 2 -> 5 -> 2`，且 `x = 3`。
那么分割后的链表应该是 `1 -> 2 -> 2 -> 4 -> 3 -> 5`。
### PHP 代码示例
```php
val = $val;
$this->next = $next;
}
}
function partition($head, $x) {
// 初始化两个哑结点
$beforeHead = new ListNode(0);
$afterHead = new ListNode(0);
$before = $beforeHead;
$after = $afterHead;
while ($head !== null) {
if ($head->val < $x) {
$before->next = $head;
$before = $before->next;
} else {
$after->next = $head;
$after = $after->next;
}
$head = $head->next;
}
// 连接两个链表
$before->next = $afterHead->next;
$after->next = null;
return $beforeHead->next;
}
// 辅助函数：构建链表
function createList($arr) {
$head = new ListNode(array_shift($arr));
$current = $head;
foreach ($arr as $val) {
$current->next = new ListNode($val);
$current = $current->next;
}
return $head;
}
// 辅助函数：打印链表
function printList($head) {
while ($head !== null) {
echo $head->val . " ";
$head = $head->next;
}
echo "\n";
}
// 示例
$head = createList([1, 4, 3, 2, 5, 2]);
$x = 3;
$result = partition($head, $x);
printList($result); // 输出: 1 2 2 4 3 5
?>
```
### Python 代码示例
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def partition(head, x):
before_head = ListNode(0)
after_head = ListNode(0)
before = before_head
after = after_head
while head:
if head.val < x:
before.next = head
before = before.next
else:
after.next = head
after = after.next
head = head.next
before.next = after_head.next
after.next = None
return before_head.next
# 辅助函数：构建链表
def create_list(arr):
head = ListNode(arr[0])
current = head
for val in arr[1:]:
current.next = ListNode(val)
current = current.next
return head
# 辅助函数：打印链表
def print_list(head):
while head:
print(head.val, end=' ')
head = head.next
print()
# 示例
head = create_list([1, 4, 3, 2, 5, 2])
x = 3
result = partition(head, x)
print_list(result) # 输出: 1 2 2 4 3 5
```
### JavaScript 代码示例
```javascript
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function partition(head, x) {
let beforeHead = new ListNode(0);
let afterHead = new ListNode(0);
let before = beforeHead;
let after = afterHead;
while (head !== null) {
if (head.val < x) {
before.next = head;
before = before.next;
} else {
after.next = head;
after = after.next;
}
head = head.next;
}
before.next = afterHead.next;
after.next = null;
return beforeHead.next;
}
// 辅助函数：构建链表
function createList(arr) {
let head = new ListNode(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
// 辅助函数：打印链表
function printList(head) {
let result = [];
while (head !== null) {
result.push(head.val);
head = head.next;
}
console.log(result.join(' '));
}
// 示例
let head = createList([1, 4, 3, 2, 5, 2]);
let x = 3;
let result = partition(head, x);
printList(result); // 输出: 1 2 2 4 3 5
```
以上代码均实现了题目要求的功能，并提供了构建链表和打印链表的辅助函数以便测试。