> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/linked_list/singly-linked-list/partition-list.md).

# Partition List

## Question ([LC.86](https://leetcode.com/problems/partition-list/description/))

> Given a singular linked list and a pivot value, partition the list into two parts (< and >=).

Preserve the original relative order of the nodes.

## Example

```
I: 1->4->3->2->5->2, 3
O: 1->2->2->4->3->5
```

## Approach

Create 2 new lists with dummy heads. Then splice them together.

## Code

```java
public ListNode partition(ListNode head, int pivot) {
    if (head == null) return null;
    // Step 0 Create two lists    
    ListNode d1 = new ListNode(0), l1 = d1;
    ListNode d2 = new ListNode(0), l2 = d2;
    // Step 1 Partition / Assign nodes
    ListNode travel = head;
    while (travel != null) {
        if (travel.val < pivot) {
            l1.next = travel;
            l1 = l1.next;
        } else {
            l2.next = travel;
            l2 = l2.next;
        }
        travel = travel.next;
    }
    // Step 2 Splice
    l2.next = null;
    l1.next = d2.next;
    return d1.next;
}
```

Running examples by hand is always important. The result might have a cycle if you don't set `l2.next` to `null`.