# [LeetCode] 86. Partition List 划分链表

2021年09月15日 阅读数：1

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

You should preserve the original relative order of the nodes in each of the two partitions.java

Example:node

```Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5```

Java:post

```public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0);  //dummy heads of the 1st and 2nd queues
ListNode curr1 = dummy1, curr2 = dummy2;      //current tails of the two queues;
}else {
}
}
curr2.next = null;          //important! avoid cycle in linked list. otherwise u will get TLE.
curr1.next = dummy2.next;
return dummy1.next;
}
```

Python:url

```# Time:  O(n)
# Space: O(1)
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def __repr__(self):
if self:
return "{} -> {}".format(self.val, repr(self.next))

class Solution(object):
# @param x, an integer
# @return a ListNode
dummySmaller, dummyGreater = ListNode(-1), ListNode(-1)
smaller, greater = dummySmaller, dummyGreater

smaller = smaller.next
else:
greater = greater.next

smaller.next = dummyGreater.next
greater.next = None

return dummySmaller.next
```

C++:orm

```// Time:  O(n)
// Space: O(1)
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode dummy_smaller{0};
ListNode dummy_larger{0};
auto smaller = &dummy_smaller;
auto larger = &dummy_larger;

smaller = smaller->next;
} else {
larger = larger->next;
}
}
smaller->next = dummy_larger.next;
larger->next = nullptr;

return dummy_smaller.next;
}
};
```

C++:htm

```ListNode *partition(ListNode *head, int x) {
ListNode node1(0), node2(0);
ListNode *p1 = &node1, *p2 = &node2;
else
}
p2->next = NULL;
p1->next = node2.next;
return node1.next;
}
```