Разделить связанный список на 3 связанных списка

Question

Проблема состоит в том, чтобы написать алгоритм для эффективного разделения заданного связанного списка на три почти эквивалентных связанных списка, т.е.

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}

Мое решение делает следующее:

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

но вышеприведенный алгоритм требует O (n) времени и O (n) пространства. Можно ли сделать это лучше?

Решение: основано на подсказках от ChrisH. Эта альтернатива занимает O (n) времени, но постоянное дополнительное пространство (для временных владельцев)

    
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

Звучит как домашняя работа, поэтому я собираюсь дать подсказку, а не полный ответ.

Вы не найдете алгоритм, который работает менее чем за O (n) времени, потому что разбиение чего-либо на части равного размера требует знания размера целого, а поиск длины связанного списка требует O (n).

Но вы можете решить эту проблему только с O (1) лишним пробелом. Ключом к решению является то, что вам нужно только найти точки в списке, где вы должны сократить его. Эти точки должны быть разделены примерно равным количеством узлов.

Чтобы узнать длину списка, необходим итератор для посещения каждого узла. Что требуется для того, чтобы знать 1/3 длины и что нужно для того, чтобы знать 2/3 длины? Я думаю, что ответ представится, если вы будете думать в том же духе.

Answer 2

Будет ли это работать?

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

решение похоже на поиск n-го элемента с конца в односвязном списке.вместо двух указателей, используемых там, нам нужно использовать три указателя с переменной скоростью, чтобы решить этот вопрос (код уже указан выше)

Answer 4

Вы не можете выполнить любую операцию, которая переходит в середину связанного списка менее чем за O (N), потому что вы не можете попасть в середину списка, не пройдя каждый узел с одного из концов.

Если ваш список неизменен, вы не можете сделать лучше, чем O (N) в пространстве, потому что единственный бит, который вы можете использовать повторно, это последняя треть.Если вы можете изменить свой список, разделив его на трети, вы можете сделать это в пространстве O (1), повторно используя все узлы и просто исключив указатель tail или next в первых двух цепочках.