#include <stdio.h>
#include <stdlib.h>

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode {
    int val;
    struct ListNode *next;
};
struct ListNode* partition(struct ListNode* head, int x) {
	struct ListNode *hl = NULL;
	struct ListNode *tl = NULL;
	struct ListNode *hg = NULL;
	struct ListNode *tg = NULL;
	struct ListNode *tmp;

	if(head == NULL) return head;
	
	for(; head != NULL; head = head->next) {
		tmp = malloc(sizeof(struct ListNode));
		tmp->val = head->val;
		tmp->next = NULL;
		if(head->val < x) {
			if(tl == NULL)
				hl = tl = tmp;
			else {
				tl->next = tmp;
				tl = tl->next;
			}
		}
		else {
			if(tg == NULL)
				hg = tg = tmp;
			else {
				tg->next = tmp;
				tg = tg->next;
			}
		}
	}

	if(hl != NULL) {
		tl->next = hg;
	} else
		return hg;

	return hl;
}