本文共 1013 字，大约阅读时间需要 3 分钟。

题目地址：

给定一个链表，再给定一个数$x$，要求按原链表的顺序，重排链表使得小于$x$的节点放在大于等于$x$的节点之前。

思路是先将整个链表按照与$x$的大小关系分成两部分，然后再接起来即可。代码如下：

public class Solution {       /**     * @param head: The first node of linked list     * @param x: An integer     * @return: A ListNode     */    public ListNode partition(ListNode head, int x) {           // write your code here        ListNode l1 = new ListNode(0), l2 = new ListNode(0);        ListNode prev1 = l1, prev2 = l2;        while (head != null) {           	// 如果当前节点小于x则接在prev1后面，否则接在prev2后面            if (head.val < x) {                   prev1.next = head;                prev1 = prev1.next;            } else {                   prev2.next = head;                prev2 = prev2.next;            }            head = head.next;        }                prev1.next = prev2.next = null;        prev1.next = l2.next;        return l1.next;    }}class ListNode {       int val;    ListNode next;    ListNode(int x) {           val = x;    }}

时间复杂度$O(n)$，空间$O(1)$。