# Leetcode 86 Partition List

## 題解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # Time complexity: O(n)
        # Space complexity: O(1)
        cur = head
        l,r = ListNode(),ListNode()
        left,right = l,r
        while cur:
            if cur.val < x: # left
                left.next = cur
                left = left.next
            else: # right
                right.next = cur
                right = right.next
            cur = cur.next
        right.next = None
        left.next = r.next
        return l.next