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;
}

prev_2.next = null;
prev_3.next = null;

}
```
-
if you do a 2 pass, one for size and one for segmentation you would have O(n) time and O(1) space, but you would do 2 passes on the linked list – Asaf Apr 17 '11 at 5:38
@Asaf: thanks for your comment. second pass is not required. pls refer to the solution above. – Riyaz Apr 17 '11 at 9:00

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.

-
its an interview question actually which i did flunk. i got the solution from your hint. thanks. – Riyaz Apr 17 '11 at 8:49
solution added to my original question – Riyaz Apr 17 '11 at 8:59
@Riyaz, your solution looks good. I first encountered a problem like this on the CompSci Advanced Placement test in circa 1988. – ChrisH Apr 17 '11 at 13:48

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.

-

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;
}
``````
-
absolutely...though the complexity won't be better than O(n) but this will require only 1 iteration. +1 – Terminal Apr 18 '11 at 8:12
@Terminal: I dont think better than O(n) is possible. – Rumple Stiltskin Apr 18 '11 at 8:36
stiltskin: No doubt about that. – Terminal Apr 18 '11 at 13:25
the solution is cleaner than mine. the difference being your code adds the last (ll_size % 3) nodes to ll_3, whereas mine distributes them among ll_1 & ll_2 – Riyaz Apr 19 '11 at 12:16

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)

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}