# 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/)