Leetcode: Partition List (#86) solution and explanation

Problem

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:
Input: head = [2,1], x = 2
Output: [1,2]
Constraints:
* The number of nodes in the list is in the range [0, 200].
* -100 <= Node.val <= 100
* -200 <= x <= 200

Solution

The idea is simple — we separately create two parts of the new list head(first part) and tail (second part).
The initial state is the following:

Firstly, let’s find an appropriate list for the first element:

It’s less than x -> goes to head:

now:

next element 4 -> goes to tail:

Every time we add new ListNode in the beginning of head or tail:

next:

finally:

As you can notice, both head and tail are in reversed order.
The next step is merging of these lists into result. Firstly, we add every element from tail, and after it — head.

This adding will be in reverse order, and in such way we’ll get resulted list in right order:

next:

All elements from tail were added. As you see, now they are in right order:

let’s add all head element in the same way: