6/26/2017 - 3:09 AM

## 86. Partition List

1. Partition List
``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type x: int
:rtype: ListNode
"""
dummy1 = ListNode(0)
dummy2 = ListNode(0)
p1 = dummy1
p2 = dummy2
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`.