# 86. Partition List

### Description

Given 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.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/partitioning-a-linked-list-around-a-given-value-and-keeping-the-original-order/)
* [Leetcode](https://leetcode.com/problems/partition-list/)
* [ProgramCreek](https://www.programcreek.com/2013/02/leetcode-partition-list-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:**

head = 1 -> 4 -> 3 -> 2 -> 5 -> 2, 

x = 3

**Output:** 1 -> 2 -> 2 -> 4 -> 3 -> 5
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="ListNode" %}

```java
// Definition for singly-linked list.
public class ListNode {
	int val;
	ListNode next;
	
	ListNode() {}
	
	ListNode(int val) { this.val = val; }
	
	ListNode(int val, ListNode next) { 
		this.val = val; 
		this.next = next;
	}
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N), where N is the number of nodes in the original linked 
 *    list and we iterate the original list.
 * Space complexity : O(1), we have not utilized any extra space, the point to 
 *    note is that we are reforming the original list, by moving the original 
 *    nodes, we have not used any extra space as such.
 */

class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null) return head;
        
        ListNode smaller = new ListNode(0);
        ListNode smallerHead = smaller;
        ListNode greater = new ListNode(0);
        ListNode greaterHead = greater;
        
        while(head != null) {
            if(head.val < x) {
                smaller.next = head;
                smaller = smaller.next;
            } else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }
        
        greater.next = null;
        smaller.next = greaterHead.next;
        
        return smallerHead.next;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

* Traverse Linked List from middle to left-right order using recursion - [GFG](https://www.geeksforgeeks.org/traverse-linked-list-from-middle-to-left-right-order-using-recursion/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/partition-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.