#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @Time: 2019/3/24
# @Author: xfLi
# The file...

"""
问题分析：
设置两个指针，h1和h2，遍历链表形成两个子链表，h1存放小于x的节点，h2存放大于等于x的节点。
"""

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def partition(head, x):
    h1 = ListNode(0)  # 存放小于x的节点
    h2 = ListNode(0)  # 存放大于等于x的节点
    h1_head = h1  # h1 头节点
    h2_head = h2  # h2 头节点
    cur = head
    while cur: # 循环完之后h1, h2 成为尾节点
        if cur.val < x:
            h1.next = cur
            h1 = h1.next
        else:
            h2.next = cur
            h2 = h2.next
        cur = cur.next
    h1.next = h2_head.next
    h2.next = None
    return h1_head.next