Как поочередно разделить двусвязный список

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

Начиная со списка вроде:

head -> 1 -> 2 -> 3 -> 4 -> 6 -> null

относительно легко работать в группах из двух узлов и распределять их по новым спискам. В основном вы начинаете с проверки наличия двух или более узлов в списке, в противном случае первый возвращаемый список является исходным, а второй список пуст.

После того, как вы это проверите, настройте указатели заголовков для возвращаемых списков, а также блуждающие указатели, чтобы отслеживать последний элемент в каждом списке:

second ------|
first --|    |
head -> 1 -> 2 -> 3 -> 4 -> 6 -> null
fEnd ---|    |
sEnd --------|

Затем, упрощенно, вы выполняете следующие шаги:

• Установите следующее значение fEnd как следующее значение sEnd (так что 1 теперь указывает на 3), затем переместите указатель fEnd на 3.
• Установите следующее значение sEnd как следующее значение fEnd (так что 2 теперь указывает на 4), затем переместите указатель sEnd на 4.

Теперь у вас есть такая ситуация:

sEnd --------------------|
fEnd ---------------|    |
           ________ |    |
          /        \     |
first/ -> 1    2    3 -> 4 -> 6 -> null
 head          |\        /
               | \______/
second --------|

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

Вы просто продолжаете делать это, пока не дойдете до конца списка.

Теперь вы заметите слово «упрощенно», упомянутое выше. Хотя описанная здесь концепция проста, есть несколько усложняющих факторов.

Во-первых, у вас может быть возможность обрабатывать группы из двух узлов просто потому, что в списке может быть нечетное количество узлов. Во-вторых, есть обычные проблемы с концами связанных списков, где вы должны быть осторожны с такими вещами, как:

node->next->prev = node;

где node может быть в конце, что может вызвать сбои при разыменовании node->next.

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

#include <stdio.h>
#include <stdlib.h>

typedef struct sNode {
    int value;
    struct sNode *next;
    struct sNode *prev;
} tNode;

static void dump (char *desc, tNode *head) {
    printf ("Dumping %s: ", desc);
    tNode *p = head;
    while (p != NULL) {
        if ((p != head) && (p->prev->next != p)) {
            printf ("double-link error\n");
            exit (1);
        }
        printf ("%d -> ", p->value);
        p = p->next;
    }
    puts ("NULL");
}

Во-вторых, «мясо» решения, функция split() в соответствии с вашими требованиями, которая принимает один список и возвращает два списка, каждый с чередующимися значениями из оригинала:

void split (tNode* head, tNode **pFirst, tNode **pSecond) {
    // Must have two elements or more to split.

    if ((head == NULL) || (head->next == NULL)) {
        *pFirst = head;
        *pSecond = NULL;
        return;
    }

    // Set up list heads and roving pointers.

    tNode *first = head, *second = head->next;
    tNode *fEnd = first, *sEnd = second;

    // Do whole list in groups of two, but check to ensure
    //   no crashes due to invalid pointer dereferences.

    while (fEnd != NULL) {
        // First in group of two.

        if (sEnd != NULL) {
            fEnd->next = sEnd->next;
            if (fEnd->next != NULL)
                fEnd->next->prev = fEnd;
        }
        if (fEnd != NULL)
            fEnd = fEnd->next;

        // Second in group of two.

        if (fEnd != NULL) {
            sEnd->next = fEnd->next;
            if (sEnd->next != NULL)
                sEnd->next->prev = sEnd;
        }
        if (sEnd != NULL)
            sEnd = sEnd->next;
    }

    // Return lists to caller.

    *pFirst = first;
    *pSecond = second;
}

Как упоминалось ранее, эта функция также влияет на исходный список, поскольку она должна использовать исходные узлы, и изменение значений next/prev в этих узлах также преобразует исходный список.

Последний фрагмент кода — это тестовая программа, которая просто дает вам список возрастающих целых чисел в каждом узле (размер зависит от любого аргумента, который вы указываете, или десяти, если вы не указываете ни одного).

Он создает список и выводит его, затем вызывает функцию split() и показывает вам результаты:

int main (int argc, char *argv[]) {
    int quant = (argc > 1) ? atoi (argv[1]) : 10;
    tNode *head = NULL, *first, *second;

    for (int i = quant - 1; i >= 0; i--) {
        tNode *add = malloc (sizeof (*add));
        add->value = i + 1;
        add->next = head;
        add->prev = NULL;
        if (head != NULL) head->prev = add;
        head = add;
    }

    dump ("before", head);
    split (head, &first, &second);
    dump ("after (first) ", first);
    dump ("after (second)", second);

    return 0;
}

Результат работы этой программы можно увидеть в следующей расшифровке:

$ ./testprog 0
Dumping before: NULL
Dumping after (first) : NULL
Dumping after (second): NULL

$ ./testprog 1
Dumping before: 1 -> NULL
Dumping after (first) : 1 -> NULL
Dumping after (second): NULL

$ ./testprog 2
Dumping before: 1 -> 2 -> NULL
Dumping after (first) : 1 -> NULL
Dumping after (second): 2 -> NULL

$ ./testprog 3
Dumping before: 1 -> 2 -> 3 -> NULL
Dumping after (first) : 1 -> 3 -> NULL
Dumping after (second): 2 -> NULL

$ ./testprog
Dumping before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> NULL
Dumping after (first) : 1 -> 3 -> 5 -> 7 -> 9 -> NULL
Dumping after (second): 2 -> 4 -> 6 -> 8 -> 10 -> NULL

$ ./testprog 9
Dumping before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
Dumping after (first) : 1 -> 3 -> 5 -> 7 -> 9 -> NULL
Dumping after (second): 2 -> 4 -> 6 -> 8 -> NULL

Мы также можем использовать операции с очередью и переменную типа bool или int для
переключения между списками назначения.

altsplit(L:List;var L1,L2:List)
   L1.head = NIL;
   L1.tail = NIL;
   L2.head = NIL;
   L2.tail = NIL;
   s = false
   while not isEmpty(L) do
        x = dequeue(L)
        if not s then
             enqueue(L1,x)
        else
             enqueue(L2,x);
        s := not s;

Обратите внимание, что нам не нужно выделять память для новых узлов
Мы просто устанавливаем указатели так же, как и в очереди.