Here is a step-by-step solution in Python:

1. Initialize two new linked lists, `before` and `after`. These will hold the nodes that are less than `x` and greater than or equal to `x` respectively.

```python
before = before_head = ListNode(0)
after = after_head = ListNode(0)
```

2. Iterate through the original linked list. For each node, check if its value is less than `x`. If it is, append it to the `before` list. If it's not, append it to the `after` list.

```python
while head:
if head.val

Question

Here is a step-by-step solution in Python:

1. Initialize two new linked lists, `before` and `after`. These will hold the nodes that are less than `x` and greater than or equal to `x` respectively.

```python
before = before_head = ListNode(0)
after = after_head = ListNode(0)
```

2. Iterate through the original linked list. For each node, check if its value is less than `x`. If it is, append it to the `before` list. If it's not, append it to the `after` list.

```python
while head:
    if head.val < x:
        before.next = head
        before = before.next
    else:
        after.next = head
        after = after.next
    head = head.next
```

3. After the iteration, the `after` list might still have a reference to some of the nodes in the `before` list. To break this reference, set the next node of `after` to `None`.

```python
after.next = None
```

4. Then, connect the `before` list with the `after` list.

```python
before.next = after_head.next
```

5. The `before_head` now is the head of the partitioned linked list. Return `before_head.next`.

```python
return before_head.next
```

Here is the complete code:

```python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def partition(head, x):
    before = before_head = ListNode(0)
    after = after_head = ListNode(0)

while head:
        if head.val < x:
            before.next = head
            before = before.next
        else:
            after.next = head
            after = after.next
        head = head.next

after.next = None
    before.next = after_head.next

return before_head.next
```

This solution works in O(n) time complexity, where n is the number of nodes in the linked list, and O(1) space complexity, as we are not using any extra space that scales with the input size.

Knowee AI · Accepted Answer