题目描述

分隔链表：给定一个链表和一个特定值 x，将链表分为两个部分，所有小于 x 的节点放在所有大于或等于 x 的节点之前，并且保持原有的相对顺序。

示例：

假设链表为 1 -> 4 -> 3 -> 2 -> 5 -> 2，且 x = 3。

那么分割后的链表应该是 1 -> 2 -> 2 -> 4 -> 3 -> 5。

PHP 代码示例

<?php

class ListNode {
    public $val;
    public $next;
    
    function __construct($val = 0, $next = null) {
        $this->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 代码示例

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 代码示例

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

以上代码均实现了题目要求的功能，并提供了构建链表和打印链表的辅助函数以便测试。