题目描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

样例

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

算法分析

模拟

• 1、枚举整个链表，若当前元素小于 x，则加入到small链表中，若当前元素大于等于 x，则加入到big链表中，使得元素以x分类
• 2、将small的末尾元素指向big的开头元素
• 3、将big的末尾元素指向null
• 4、返回small.next

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode p = head;
        ListNode ps = small;
        ListNode pb = big;

        while(p != null)
        {
            if(p.val < x)
            {
                ps.next = p;
                ps = ps.next;
            }
            else
            {
                pb.next = p;
                pb = pb.next;
            }
            p = p.next;
        }
        pb.next = null;
        ps.next = big.next;

        return small.next;
    }
}