## Microsoft Interview Question

Software Developers**Country:**India

**Interview Type:**Written Test

public static Node alRev(Node head)

{

if (head == null) return head;

if (head.next != null)

{

if (head.next.next != null)

{

Node n = head.next;

head.next = head.next.next;

n.next = null;

Node temp = alRev(head.next);

if (temp != null){

temp.next = n;

return n;

}

}

else

return head.next;

}

else

return head;

return null;

}

Iterate through all list nodes and put the alternate nodes on to stack. Time complexity of O(N) and space complexity of S(N/2).

```
public Node ReverseAlternateNodes(Node head){
/*
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 1 -> 3 - > 5 -> 6 -> 4 -> 2
*/
Node temp = head;
Stack<Node> stck = new Stack<Node>();
while (temp.Next != null){
var next = temp.Next.Next;
var reverseItem = temp.Next;
//Null out the reversedNode next item.
reverseItem.Next = null;
//Push the next node on to the stack;
stck.Push(reverseItem);
//Assign Next.Next to current next;
temp.Next = next;
if(temp.Next != null){
temp = temp.Next;
continue;
}
break;
}
while(stck.Count > 0){
temp.Next = stck.Pop();
//Console.WriteLine(temp.Next.Val);
temp = temp.Next;
}
return head;
}
```

```
public Node ReverseAlternateNodes(Node head){
/*
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 1 -> 3 - > 5 -> 6 -> 4 -> 2
*/
Node temp = head;
Stack<Node> stck = new Stack<Node>();
while (temp.Next != null){
var next = temp.Next.Next;
var reverseItem = temp.Next;
//Null out the reversedNode next item.
reverseItem.Next = null;
//Push the next node on to the stack;
stck.Push(reverseItem);
//Assign Next.Next to current next;
temp.Next = next;
if(temp.Next != null){
temp = temp.Next;
continue;
}
break;
}
while(stck.Count > 0){
temp.Next = stck.Pop();
//Console.WriteLine(temp.Next.Val);
temp = temp.Next;
}
return head;
}
```

- Alex November 30, 2017