Сторнирование односвязного списка при задании размера блока - PullRequest
Новая
       11

Сторнирование односвязного списка при задании размера блока

4 голосов
/ 08 августа 2011

Существует односвязный связанный список и указан размер блока. Например, если мой связанный список равен 1->2->3->4->5->6->7->8-NULL, а мой размер блока равен 4, то поменяйте местами первые 4 элементы, а затем вторые 4 элемента. Вывод задачи должен быть 4->3->2->1->8->7->6->5-NULL

Я думал о том, чтобы разделить связанный список на сегменты размером 4 и затем обратить его вспять. Но таким образом я вынужден использовать много дополнительных узлов, что вовсе не желательно. Сложность пространства должна быть сведена к минимуму.

Будет весьма замечательно, если кто-то сможет найти лучшее решение, в котором использование дополнительных узлов будет сведено к минимуму.

Ответы [ 3 ]

2 голосов
/ 08 августа 2011

Я попробовал это ... кажется, работает нормально ... 

node* reverse(node* head) // function to reverse a list
{
    node* new_head = NULL;
    while(head != NULL)
    {
        node* next = head->next;
        head->next = new_head;
        new_head = head;
        head = next;
    }
    return new_head;
}

node* reverse_by_block(node* head, int block)
{
    if(head == NULL)
            return head;

    node* tmp = head;
    node* new_head = head;
    node* new_tail = NULL;

    int count = block;
    while(tmp != NULL && count--)
    {
        new_tail = tmp;
        tmp = tmp->next;
    }

    new_tail->next = NULL;
    new_tail = new_head;
    new_head = reverse(new_head);
    new_tail->next = reverse_by_block(tmp,block);

    return new_head;
}
0 голосов
/ 11 августа 2011

Это можно сделать в линейном времени с постоянным пространством.Вот краткое описание:

  1. Разделите связанный список на две части по размеру блока 

    
int split(node* head, node** listA, node** listB size_t block_size)
{
node* cur = head;

while(block_size && cur)
{
   cur = cur->next;
   --block_size;
}
if(!cur) { /* error : invalid block size */ return -1; }
*listA = head;
*listB = cur->next;
cur->next = NULL; /* terminate list A */
return 0;
}

  2. Обратный ход двух подразделов, (используйте нерекурсивную линейную функцию времени, константы) 

    
reverse(listA);
reverse(listB);

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

    
cur = *listA;
/* goto last but one element of listA */
while(cur->next) cur = cur->next; 
cur->next = *listB;
0 голосов
/ 08 августа 2011

Вы можете заранее поменять местами текущий элемент со следующими 3 раза: 1234, 2134, 2314, 2341. Затем сделайте это дважды, чтобы получить 3421. Затем один раз, чтобы получить 4321. Затем выполните 4 шага и повторите процесс со следующим блоком. .

...