Interview Question
Country: India
c# implementation.
key function.
private static void ReverseKBatchNodes<T>( ref Node<T> headNode, int k ) {
if ( headNode == null ) { return; }
Node<T> prevNodeBeforeGroup = GetPrevNodeBeforeGroup( headNode, k );
if ( prevNodeBeforeGroup == null ) { return; }
Node<T> currNode = prevNodeBeforeGroup.NextNode;
int counter = -1;
while ( currNode != null ) {
counter++;
if ( counter < k - 1 && currNode.NextNode != null) {
currNode = currNode.NextNode;
continue;
}
var tmpHead = prevNodeBeforeGroup.NextNode;
prevNodeBeforeGroup.NextNode = currNode.NextNode;
currNode.NextNode = headNode;
headNode = tmpHead;
currNode = prevNodeBeforeGroup.NextNode;
counter = -1;
}
}
another part of code for testing the solution.
private static Node<T> GetPrevNodeBeforeGroup<T>( Node<T> headNode, int k ) {
Node<T> prevNodeBeforeGroup = null;
var currNode = headNode;
for ( int i = 0; i < k - 1; i++ ) {
prevNodeBeforeGroup = currNode.NextNode;
currNode = currNode.NextNode;
if ( currNode == null ) { return null; }
}
return prevNodeBeforeGroup;
}
private const int limit = 9;
private const int K = 2;
private static Node<int> CreateSinglyLinkedList( int n = 1 ) {
var node = new Node<int> { Data = n };
if ( n < limit ) {
node.NextNode = CreateSinglyLinkedList( ++n );
}
return node;
}
public class Node<T> {
public T Data { get; set; }
public Node<T> NextNode { get; set; }
}
static void Main(string[] args) {
Node<int> headNode = CreateSinglyLinkedList();
ReverseKBatchNodes( ref headNode, K );
var currNode = headNode;
while ( currNode != null ) {
Console.Write( $"{currNode.Data} " );
currNode = currNode.NextNode;
}
Console.ReadLine();
}
- siva.sai.2020 November 26, 2015