Thursday, June 2, 2011

From list of lists to list

Given a linked list structure where every node represents a linked list and contains two pointers of its type:
(i) pointer to next node in the main list.
(ii) pointer to a linked list where this node is head.
Write a C function to flatten the list into a single linked list.

1 comment:

  1. How about this:

    struct NodeT;
    typedef struct NodeT Node;

    struct NodeT {
    Node* m_next_main;
    Node* m_next_sublist;
    };

    /*
    * Flattens a sublist, returns a pointer to the last element in the list.
    */

    Node* flatten(Node* head)
    {
    Node* last;
    Node* n;

    for (n = head; n; n = n->m_next_main) {
    last = n;

    if (n->m_next_sublist) {
    Node* t = n->m_next_main;
    n->m_next_main = n->m_next_sublist;
    n->m_next_sublist = 0;
    flatten(n)->m_next_main = t;
    }
    } while ((n = n->m_next_main) != 0);

    return last;
    }

    ReplyDelete