Table of Contents

## Question

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 = 3Output:[1,2,2,4,3,5]

**Example 2:**

Input:head = [2,1], x = 2Output:[1,2]

**Constraints:**

- The number of nodes in the list is in the range
`[0, 200]`

. `-100 <= Node.val <= 100`

`-200 <= x <= 200`

## Python Solution

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def partition(self, head: ListNode, x: int) -> ListNode: l1 = ListNode(0) y = l1 l2 = ListNode(0) z = l2 head1 = head while head1: if head1.val < x: l1.next = ListNode(head1.val) l1 = l1.next else: l2.next = ListNode(head1.val) l2 = l2.next head1 = head1.next l1.next = z.next return y.next