Leetcode - Reverse Nodes in k Group

Question

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.

Ideas

• MEMORIZE MEMORIZE MEMORIZE
• The entire idea here is that we want to reverse the list in segments
• When we reverse a segment, we are detaching it from the rest of the list because we are messing with our pointers so we need a way to reconnect the previous group to our reversed segment and our reversed segment to our next group
• We can maintain a dummy pointer that points to the head to prevent errors
• We need to also track our previous group which we can initialize to our dummy
• Make an API from Linked List which reverses a linked list starting at a node and going to another node
• starting from prev node (make a copy of this), we want to traverse the linked list +k positions
• our next segment is now kth.next
• the segment we want to reverse is prev.next
• we can use our API and store it in a newHead that is our reversed segment
• now we want to reconnect this segment by:
  • setting prev.next to newHead
  • setting groupHead.next to our next segment (since this pointer is now the tail)
  • setting prev = groupHead

Solution