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。然后执行两次以获得 3421。然后执行一次以获得 4321。然后前进 4 步并在下一个块中重复该过程。

于 2011-08-08T13:24:43.197 回答
0

这可以在具有恒定空间的线性时间中完成。以下是简要说明：

  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;
于 2011-08-11T05:35:58.373 回答