用两个链表分别记录<x的节点和>=x的节点。

Use two linked lists to separately record nodes < x and nodes >= x.

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

class Solution:
    # @param head, a ListNode
    # @param x, an integer
    # @return a ListNode
    def partition(self, head, x):
        if head == None: return None
        headLess = currLess = ListNode(0)  # dummy node
        headGreater = currGreater = ListNode(0)  # dummy node
        prev, curr = None, head
        while curr:
            prev, curr = curr, curr.next
            if prev.val < x:
                currLess.next, currLess, currLess.next = prev, prev, None
            else:
                currGreater.next, currGreater, currGreater.next = prev, prev, None
        currLess.next = headGreater.next
        return headLess.next