Split a linkedlist into 3 linkedlists

Question

The problem is to write an algorithm to split a given linkedlist efficiently into three almost-equivalent linkedlists, i.e.

if we have a linkedlist {1->5->7->9->2->4->6} the output should be   
LL_1={1->5->7}, LL_2={9->2}, LL_3={4->6}

My solution does the following:

1-iterate the given linkedlist from start to end
2-at each node cache the nodes reference into an array, say ll_array
3-now we have the linkedlists size (ll_array.lenght) and all the node references 
  in an array which we can use to create the three linkedlists in a 
  straightforward manner

but the above algorithm requires O(n) time and O(n) space. Can this be done better?

Solution: based on hints from ChrisH. This alternative takes O(n) time but constant extra space (for the temporary holders)

    
Node {
    String value;
    Node next;
}
split(Node rootNode /*root node of input linked-list*/) {
    // root node of the three resulting linked-lists
    Node root_1 = rootNode;
    Node root_2 = null;
    Node root_3 = null;

    // previous nodes of linked-lists 2 & 3 (since ours is a singly-linked-list)
    Node prev_2 = null;
    Node prev_3 = null;

    int count = 0; // counter
    Node currentNode = rootNode; // temp holder

    while(currentNode != null) {
        count++;

        if (count > 3) {
            int mod = count % 3;
            if (mod == 1) {
                prev_2 = root_2;
                root_2 = root_2.next;

                prev_3 = root_3;
                root_3 = root_3.next;
            } else if (mod == 2) {
                prev_3 = root_3;
                root_3 = root_3.next;
            }
        } else if (count == 2) { // initialize linked-list-2
            root_2 = currentNode;
        } else if (count == 3) { // initialize linked-list-3
            root_3 = currentNode;
        }

        currentNode = currentNode.next;
    }

    // unlink linked-lists 2 & 3 from the chain 
    prev_2.next = null; 
    prev_3.next = null;

}

Answer 1

This sounds like homework so I'm going to provide a hint rather than a full answer.

You will not find an algorithm that runs in less than O(n) time because splitting something into equal size parts requires knowing the size of the whole, and finding the length of a linked list requires O(n).

But you can solve this problem with only O(1) extra space. The key to the solution is that you only need to find the points in the list where you need to cut it. Those points should be separated by roughly equal numbers of nodes.

Knowing the length of the list requires an iterator to visit every node. What is required to know 1/3 of the length and what is required to know 2/3 of the length? I think the answer will present itself if you think along those lines.

Answer 2

Will this work?

int split_list(struct node *ll)
{
    struct node *l1, *l2, *l3;
    if(!(ll && ll->next && ll->next->next)){
        printf("Need atleast 3 elements\n");
        return -1;
    }
    l1 = ll;
    l2 = ll->next;
    l3 = ll->next->next;
    while(l3 && l3->next && l3->next->next){
        l1 = l1->next;
        l2 = l2->next->next;
        l3 = l3->next->next->next;
    }
    l3 = l2->next;
    l2->next = NULL;
    l2 = l1->next;  
    l1->next = NULL;
    l1 = ll;
    printf("l1:%d, l2=%d, l3=%d\n", l1->data, l2->data, l3->data);

    return 0;
}

Answer 3

solution is similar to find the nth element from the end in a singly linked list. instead of two pointers used there, we need to use three pointers with varying speed to solve this question (code is already given above)

Answer 4

You can't do any operation that goes to the middle of a linked list in less than O(N) time because you can't get to the middle of the list without traversing every node from one of the ends.

If your list is immutable, you can't do any better than O(N) in space either, because the only bit you can reuse is the last third. If you can modify your list to split it into thirds, you can do it in O(1) space by reusing all the nodes and just eliminating the tail or next pointer in the first two chains.