###### tags: `Leetcode` `medium` `list` `python`

# 86. Partition List

## [題目連結:] https://leetcode.com/problems/partition-list/

## 題目:
Given the ```head``` of 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.


#### [圖片來源:] https://leetcode.com/problems/partition-list/

## 解題想法:
* 題目為，給定一值x，讓list重組為前半段小於x，後半段大於等於x
* 分別設兩個dummy node，
* small:存小於x的node
* big:存大於等於x的node
* 遍歷整串list，將node逐一分配
* 最後在將small與big串聯

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        tmp = []
        while head:
            tmp.append(head.val)
            head=head.next
        print(tmp)
class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        # time: O(n)
        small = ListNode(0) #紀錄小的值
        cur_small = small
        big = ListNode(0) 
        cur_big = big
        while head:
            if head.val<x:
                cur_small.next=head
                cur_small=cur_small.next
            else:
                cur_big.next=head
                cur_big=cur_big.next
            head = head.next
        #合併
        cur_big.next=None
        cur_small.next=big.next
        return small.next

head = ListNode(1)
head.insert(4)
head.insert(3)
head.insert(2)
head.insert(5)
head.insert(2)
head.printList()

result = Solution()
ans = result.partition(head,x=3)
ans.printList()