Reverse a linked list with step K
A while ago, we used to do a first screening on the candidates applying for a developer position in our team by using the reverse linked list problem.
Last week, I found a variation that looks a bit more interesting:
Given a link list and a step K, reverse the link list in K size slots
Example Input 12--> 13--> 3--> 20--> 55--> 87--> 20--> 77--> 90 For k =3 Output 3--> 13--> 12--> 87--> 55--> 20--> 90--> 77--> 20
When I reverse a linked list in one traversal, I switch the current element with its next neighbor and make the latter point to the former head.
To write it quickly (p is the current node):
while (p.Next) { Node q = p.Next; p.Next = q.Next; q.Next = head; head = q; }
This time, since we have to create cycles of length k, we should reverse each cycle and link its end node to the beginning of the next cycle. I'm using a currentCycleHead while reversing which, for the first cycle, represents the head.
public static ListNode<T> ReverseWithStepK<T>(ListNode<T> head, int k) { if (head == null || k <= 1) { return head; } // run the k-length cycle and reverse values ListNode<T> currentCycleHead = head; int cycleLength = 1; bool firstCycle = true; // link the end of the previous cycle to the current cycle head ListNode<T> previousCycleNode = null; // use p to switch two positions var p = head; while (p.Next != null) { if (cycleLength == k) { // start new cycle firstCycle = false; cycleLength = 1; // no need to reverse this node previousCycleNode = p; p = p.Next; //for the new cycle, the head is the current node currentCycleHead = p; previousCycleNode.Next = currentCycleHead; continue; } // advance one node var q = p.Next; p.Next = q.Next; // make the switch so that the node will go to the beginning q.Next = currentCycleHead; currentCycleHead = q; if (firstCycle) { head = currentCycleHead; } else { previousCycleNode.Next = currentCycleHead; } // one more element in the cycle cycleLength++; } return head; }
