Reversing a singly linked list when setting the block size

Question

There is a separate linked list and the block size is set. For example, if my linked list is 1->2->3->4->5->6->7->8-NULL , and my block size is 4 , then cancel the first 4 elements and then 4 elements. The output of the problem should be 4->3->2->1->8->7->6->5-NULL

I was thinking about splitting the linked list into segments of size 4 , and then backwards. But in this way I have to use many additional nodes, which is undesirable at all. The complexity of the space should be minimized.

It will be very important if someone can find the best solution in which the use of additional nodes will be minimized.

Answer 1

I tried ... it 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; } 

Answer 2

You can move the current item with the following 3 times: 1234, 2134, 2314, 2341. Then do it twice to get 3421. Then once to get 4321. Then follow 4 steps and repeat the process with the next block.

Answer 3

This can be done in linear time with constant space. Here is a brief description:

• Divide the linked list into two parts by block size

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

• Flip over two parts, (use non-recursive linear time, constant space function)

   reverse(listA); reverse(listB); 

• Link them to get the desired linked list.

   cur = *listA; /* goto last but one element of listA */ while(cur->next) cur = cur->next; cur->next = *listB;