题目

86. 分隔链表

思路

本来想直接在链表上进行修改，但是发现太乱。
定义两个新的空链表，一个保存小于 x 的节点，另一个保存大于等于 x 的节点。

public ListNode partition (ListNode head, int x){
    ListNode smallNode = new ListNode(0);
    ListNode largerNode = new ListNode(0);
    ListNode small = smallNode, large = largerNode;

    while (head != null){
        if (head.val < x){
            small.next = head;
            small = small.next;
        }
        else {
            large.next = head;
            large = large.next;
        }
        head = head.next;
    }

    large.next = null;
    small.next = largerNode.next;

    return smallNode.next;
}

时空复杂度

时间复杂度：O(n)，其中 n 是原链表的长度。需要遍历原链表一次。

空间复杂度：O(1)。只需要创建了常数个额外节点。