Take the 2-minute tour ×

OK. I have an assignment in c programming course. I need to implement a function prototype which is:

void split(node* head, node **first, node **second)   

This function splits the doubly-linked list pointed by head to two lists first and second.

Assume that head holds the elements F0,S0,F1,S1,F2,S2,...


  • first should contain the elements in this order: F0,F1,F2,...
  • second should contain the elements in this order: S0,S1,S2,...

Do not make any allocations or deallocations (malloc, calloc, realloc, free). Only update pointers. Do not change node data.

Restrictions: Do not use malloc(), calloc(), realloc(),free().

I am stuck, I can't produce any algorithm. PLease, help!

typedef struct node
    int data;
    struct node *prev;
    struct node *next;
} node;


    #define DATA(p) ((p)->data)
    #define NEXT(p) ((p)->next)
    #define PREV(p) ((p)->prev)

        node* firstCurrent = head;
        node* secondCurrent = NULL;
        node* dummyforbprev = NULL;

        if ( firstCurrent )
            secondCurrent = NEXT(firstCurrent);

        *first = firstCurrent;
        *second = secondCurrent;

        while ( firstCurrent && secondCurrent )
            NEXT(firstCurrent) = NEXT(secondCurrent);
            dummyforbprev = PREV(firstCurrent);
            firstCurrent = NEXT(firstCurrent);
                PREV(firstCurrent) = PREV(secondCurrent);

            if ( firstCurrent )
                NEXT(secondCurrent) = NEXT(firstCurrent);
            PREV(secondCurrent) = dummyforbprev;
            secondCurrent = NEXT(secondCurrent);

        if ( firstCurrent )
            NEXT(firstCurrent) = NULL;

        if ( secondCurrent )
            NEXT(secondCurrent) = NULL;
share|improve this question
Show the code which you currently have. –  user694733 Jan 27 at 14:39
Set i to 0. For each node in head: Remove node from head. Append node to tail of first if i is even, append node to tail of second if odd. Increment i and loop. –  Magnus Reftel Jan 27 at 14:42
@Magnus Reftel How to remove and append a node? Can you explain? –  nualloc Jan 27 at 14:44
@M Oehm The actual problem is how can I do this without making any allocation or deallocation. No, this is not surely. I have already implemented delete_node() and insert_node() functions. –  nualloc Jan 27 at 14:53
You have the node already, so you don't need to clone it to get a new copy or anything. Just change what its next and prev pointers point to (updating the pointers in the old list to match). There's a reasonably good explanation at en.wikipedia.org/wiki/Doubly_linked_list –  Magnus Reftel Jan 27 at 14:58

Your Answer



Browse other questions tagged or ask your own question.