Data structure (conventions consistent with the Wikipedia article):

    struct half_edge;

    struct vertex {
        struct half_edge *rep;  /* rep->tail == this */
    };

    struct face {
        struct half_edge *rep;  /* rep->left == this */
    };

    struct half_edge {
        struct half_edge *prev;  /* prev->next == this */
        struct half_edge *next;  /* next->prev == this */
        struct half_edge *twin;  /* twin->twin == this */
        struct vertex *tail;
        struct face *left;
    };

Algorithm:

For each endpoint, create a vertex. For each input segment, create two half-edges and assign their tail vertices and twins. For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order. For every pair of half-edges `e1, e2` in clockwise order, assign `e1->twin->next = e2` and `e2->prev = e1->twin`. Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge `e` in the sorted list, set `e->twin->next = e` and `e->prev = e->twin`. If you do things right, this won't require extra code.) The next pointers are a permutation on half-edges. For every cycle, allocate and assign a face structure.