4

単一に接続されたリンクリストがあり、ブロックサイズが指定されています。たとえば、リンクリストが1->2->3->4->5->6->7->8-NULLで、ブロックサイズが4最初の要素を逆にして4から、次の4つの要素を逆にした場合、問題の出力は次のようになります。4->3->2->1->8->7->6->5-NULL

リンクリストをサイズのセグメントに分割して4から逆にすることを考えていました。しかし、そうすれば、まったく望ましくない多くの余分なノードを使用せざるを得なくなります。スペースの複雑さは最小限に抑える必要があります。

余分なノードの使用を最小限に抑えるより良いソリューションを誰かが提供できれば、非常に高く評価されます。

4

3 に答える 3

2

私はこれを試しました...うまくいくようです...

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;
}
于 2011-08-08T18:10:31.267 に答える
0

現在の要素を次の 3 回: 1234、2134、2314、2341 と交換して進めることができます。次に、2 回実行して 3421 を取得します。次に 1 回実行して 4321 を取得します。次に、4 つのステップを進めて、次のブロックでプロセスを繰り返します。

于 2011-08-08T13:24:43.197 に答える
0

これは、一定のスペースを使用して線形時間で実行できます。簡単な説明は次のとおりです。

  1. リンクされたリストをブロックサイズで 2 つの部分に分割する

    
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. 2 つのサブパートを逆にします (非再帰的な線形時間、定数空間関数を使用します)。

    
reverse(listA);
reverse(listB);

  3. それらをリンクして、目的のリンク リストを取得します。

    
cur = *listA;
/* goto last but one element of listA */
while(cur->next) cur = cur->next; 
cur->next = *listB;
于 2011-08-11T05:35:58.373 に答える