moonlightshadow123

6/26/2017 - 3:09 AM

- Partition List

```
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
dummy1 = ListNode(0)
dummy2 = ListNode(0)
p1 = dummy1
p2 = dummy2
p = head
while p:
if p.val < x:
p1.next = p
p1 = p1.next
p = p.next
p1.next = None
# If you are merging two lists, then you don't have to do that.
# but if you are doing in one list, you have to do set None to the last node.
# Otherwise, there will be a loop, `node1(p1)->node2(p2)`.
else:
p2.next = p
p2 = p2.next
p = p.next
p2.next = None
p1.next = dummy2.next
return dummy1.next
```

https://leetcode.com/problems/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.

For example,
Given `1->4->3->2->5->2`

and x = 3,
return `1->2->2->4->3->5`

.