Easy to read solution, O(n) running time, O(1) space


#1

The idea is to break the list into two lists one with values less than x and other with values greater than x. Once this is done, connect the tail of less to the head of greater. Similar to the odd-even problem.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* Solution::partition(ListNode* head, int x) 
{
    if(head == NULL || head->next == NULL)
        return head;
        
    ListNode *less = NULL, *greater = NULL;
    ListNode *temp = head, *next = NULL;
    ListNode *less_head = NULL, *greater_head = NULL;
    
    while(temp != NULL)
    {
        next = temp->next;
        if(temp->val < x)
        {
            if(less == NULL)
            {
                less = temp;
                less_head = less;
            }
            else
            {
                less->next = temp;
                less = less->next;
            }
        }
        else
        {
            if(greater == NULL)
            {
                greater = temp;
                greater_head = greater;
            }
            else
            {
                greater->next = temp;
                greater = greater->next;
            }
        }
        
        temp = next;
    }
    
    if(greater_head == NULL)
        return less_head;
    if(less_head == NULL)
        return greater_head;
        
    greater->next = NULL;
    less->next = greater_head;
    
    return less_head;
}

#2

It’s not O(1) space. You are creating two auxillary linked lists.


#3

I am not making two linked lists I am just splitting the same linked list into 2. So I am just using two pointers to point at the head of both of them, that’s it. I am not copying the data.


#4

Yeah sorry! My bad. You’re correct.


#5

Nice and elegant solution.