CareerCup

#include <iostream>

using namespace std;

class Node {
	public:
		Node(int val)
		{
			val_ = val;
			next_ = NULL;
		}
		int val_;
		Node *next_;
};

void AlternateReverse(Node *head)
{
	Node *head2 = NULL;
	Node *n = head;
	while (n) {
		Node *next_n = NULL;
		if (n->next_) {
			next_n = n->next_->next_;
			n->next_->next_ = head2;
			head2 = n->next_;
			n->next_ = next_n;
		}
		if (next_n == NULL) {
			n->next_ = head2;
		}
		n = next_n;
	}
}

void Print(Node *head)
{
	for (Node *n = head; n != NULL; n = n->next_) {
		cout << n->val_ << "->";
	}
	cout << "\n";
}

int main()
{
	Node n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7), n8(8), n9(9);
	n1.next_ = &n2;
	n2.next_ = &n3;
	n3.next_ = &n4;
	n4.next_ = &n5;
	n5.next_ = &n6;
	n6.next_ = &n7;
	n7.next_ = &n8;
	n8.next_ = &n9;

	Print(&n1);
	AlternateReverse(&n1);
	Print(&n1);
}

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;
    }