algorithm - 给定 block 大小时反转单向链表

Question

有一个单向连接的链表和 block 大小给定。例如，如果我的链表是 1->2->3->4->5->6->7->8- NULL 并且我的 block 大小是 4 然后反转第一个 4 元素然后是第二个 4 个元素。问题的输出应该是 4->3->2->1->8->7->6->5-NULL

我当时想把链表分成大小为4的段，然后倒过来。但是这样我就不得不使用很多根本不需要的额外节点。空间复杂度应保持在最低限度。

如果有人能提出更好的解决方案，将额外节点的使用保持在最低限度，我们将不胜感激。

Answer 1

我试过了...似乎工作正常...

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;
}