25_reverse_nodes_in_k_group

dz / leetcode / 25_reverse_nodes_in_k_group

Summary

25. Reverse Nodes in K Group. Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed.

Node Tree

• URL
• approximate_algorithm
  • reverse_list
• editorial
  • approach_1_recursion
    • recursion_works_well_for_linked_lists
• intuition
  • forgot_about_the_new_head
  • how_to_use_dummy_node
  • approach_2_iterative
    • forgot_about_the_new_head

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/reverse-nodes-in-k-group/

intuition
content	Thinking about a linked list in terms of chunks/blocks of size k. A block can be defined in terms of the start and end node. A reverse operation on a block updates the links to be reverse flow, the start becomes the end and then becomes the start. These start/end blocks then need to be properly linked to the neighboring blocks, the previous end points to the current start.
children	forgot_about_the_new_head (detail I forgot), how_to_use_dummy_node, approach_2_iterative (similar to what I thought of)

how_to_use_dummy_node
content	They keep using dummy nodes in the answers to these questions, I'm not used to thinking that way.
parents	intuition

approximate_algorithm
content	Start with the head, set to start. In a loop, iterate k times to get start/end. If no null, found, reverse segment with start/end, and swap. Link previous end to start. Set current end to previous. If null was found in current block, break.
children	reverse_list

reverse_list
content	There are multiple ways to reverse a linked list. Since k is rather large (5000), using a stack-based recursion approach is probably out of the question. A->B->C->D becomes A<-B<-C<-D. So, this should be able to be done in pairs iteratively.
parents	approximate_algorithm

editorial
content	editorial
children	approach_1_recursion

approach_1_recursion
content	Approach 1 is recursion (even though there's a space constraint). Basically start with a head, and reverse-append. There are two pointers to keep track of. "head" pointer is passed to the function call. "rev-head" is something that recursion will return to the caller. User a counter to keep track of k nodes and break when it reaches k.
children	recursion_works_well_for_linked_lists
parents	editorial

recursion_works_well_for_linked_lists
content	Recursion works well for linked lists because a subset of a linked list is another linked list.
parents	approach_1_recursion

approach_2_iterative
content	Instead of using the stack and imagining the problem recursively, introduce a few new variables. In addition to =rev= and =rev_head=, also include =ktail=, the tail of the previous k nodes after reversal, and =new_head=, the head of the final list after output.
children	forgot_about_the_new_head
parents	intuition

forgot_about_the_new_head
content	In the solution I thought up, I forgot about returning the new head, which is the kth element in the list.
parents	intuition, approach_2_iterative