问题描述
有一个单连接链表,并且给出了块大小.例如,如果我的链表是 1->2->3->4->5->6->;7->8-NULL
并且我的块大小是 4
然后反转第一个 4
元素,然后是第二个 4 个元素.问题的输出应该是 4->3->2->1->8->7->6->5-NULL
There is a singly connected linked list and a block size is given.For eg if my linked list is 1->2->3->4->5->6->7->8-NULL
and my block size is 4
then reverse the first 4
elements and then the second 4 elements.The output of the problem should be 4->3->2->1->8->7->6->5-NULL
我想将链表分成大小为 4
的段,然后将其反转.但是这样我就被迫使用了很多根本不需要的额外节点.应将空间复杂度保持在最低限度.
I was thinking of dividing the linked list into segments of size 4
and then reversing it.But that way I am forced to use a lot of extra nodes which is not desired at all.The space complexity should be kept to a minimum.
如果有人能提出更好的解决方案,将额外节点的使用保持在最低限度,那将是非常值得赞赏的.
It will be highly appreciable if someone can come with a better solution where the usage of extra nodes would be kept to a minimum.
推荐答案
我试过了...似乎工作正常...
I tried this...seems to work fine...
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;
}
这篇关于给定块大小时反转单向链表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!