CareerCup

In C, this is a pseudo code. O(n) runtime, O(1) memory. This question would be much simpler if there is a dummy head in the linked list. Asking this question would definitely impress the interviewer.
Otherwise, with the restriction on extra node creation, you will need extra 50% energy and 50% increased complexity to deal with the first node.

public node* pair_r(node* head) throw (String); //function to reverse a pair.throw String if reach end of the list.
public node* main(node* root) { //main function to reverse a linked list
    if (root.next == null) return root; //do nothing if length is 1.
    root = pair_r(root); //manually reverse first pair since lack of dummy head.
    node* cur = root.next; //set current pointer to the second node.
    while (!end) { //loop till the end of linked list
        try {cur.next = pair_r(cur.next);}//reverse
        catch (String s) {break;}//end of list, odd node
        if (cur.next == null) break; //end of list, even node
    }
    return root;
}

public node* pair_r(node* head) throw (String) {
    //linked list like: 1->2->3
    if (head.next == null) throw "end of linked list";
    node* temp = head.next; //set temp to 2nd_node
    if (temp.next != null) head.next = temp.next; //set 1st_node.next=3rd_node
    else head.next = null; //set 1st_node.next=null if hit the end of linked list
    temp.next = head; //set 2nd_node.next=1st_node
    return temp; //return pointer to 2nd_node to connect previous node.
    // linked list sorted to: 2->1->3
}

#include<iostream>

using namespace std;

typedef struct node_targ{
	char data;
	struct node_targ *next;
}Node;

Node *change(Node *root)
{
	Node *temp;
	temp = root->next->next;
	root->next->next= root;
	root = root->next;
	root->next->next = temp->next;
	temp->next = root->next->next->next;
	root->next->next->next=temp;
	return root;	
	
} 
main()
{		
	Node n5 = {'e',NULL};
	Node n4 = {'d',&n5};
	Node n3 = {'c',&n4};
	Node n2 = {'b',&n3};
	Node n1 = {'a',&n2};
	
	Node *root;
	root = &n1;
	cout<<"\n------------------before--------------------\n";
	while(root){
		cout<<root->data;
		if(root->next != NULL) cout<<"->";
		root = root->next;
	}
	cout<<"\n------------------after---------------------\n";
	
	root = change(&n1);
	while(root){
		cout<<root->data;
		if(root->next != NULL) cout<<"->";
		root = root->next;
	}
	cout<<"\n";
}

void reversepair(node * head){
if(!head || !head->next)
     return;
node* temp;
temp = head->next;
head->next = temp->next;
temp->next = head;
reversepair(head->next);
}

Here is a working code which I wrote for a general value 'k' indicating every k nodes to be reversed.
eg 1->2->3->4->5->6->7->8->9->10->11 [k=3]
answer must be [3->2->1->6->5->4->9->8->7->11->10]

For this problem put k = 2;

void ReverseK(Node** headRef, int k)
{
    Node *ptr = *headRef;
    Node *next_ptr = ptr->next;
    Node *prev_ptr = NULL;
    Node *subarray_head = *headRef;
    Node *prevsubarray_tail = NULL;
    int count = k;
    bool isHeadReset = false;
    
    while (subarray_head)
    {
        while (count-- && ptr)
        {
            next_ptr = ptr->next;
            ptr->next = prev_ptr;
            prev_ptr = ptr;
            ptr = next_ptr;
        }
        
        if (!isHeadReset)
        {
            *headRef = prev_ptr;
            isHeadReset = true;            
        }
        else
        { 
            prevsubarray_tail->next = prev_ptr; 
        }
            
        prevsubarray_tail = subarray_head;
        subarray_head = ptr;
        prev_ptr = NULL;    
        count = k;
    } 
}

yup.. this time microsoft seems to be in an easy mood... bt they are asking some irrelevant question... like how to chek if a tree is binary.. a post is on careercup,refering this irrelevant question,people are commenting its nonsense question made by poster himself.. bt believe me it is a microsoft question..

Non Recursive version with actual swapping of links(not swapping the value)

struct list* PairReverse(struct list *head)
{
struct list* curr = head;

while (curr != NULL)
{
if (curr ->link != NULL)
{
next = curr->link;
curr->link = next->link;
next->link = curr;
curr = curr->link;
}
}

if (head->link) //If there are atleast 2 elements in list than 2nd one becomes new head
return (head->link);
else
return (head); //if there is only 1 element in list.
}

Working code..

struct Link
{
	int data;
	Link * next;
};

Link* reversePairWise(Link* lnk)
{
	if(lnk == NULL ) return lnk;
	if(lnk->next == NULL ) return lnk;

	Link* t1 = lnk->next;
	lnk->next = lnk->next->next;
	t1->next = lnk;
	Link* prev = t1->next;
	lnk = t1->next->next;
	while(lnk != NULL && lnk->next != NULL )
	{
		Link* temp1 = lnk->next;
		lnk->next = lnk->next->next;
		temp1->next = lnk;
		prev->next = temp1;
		prev = prev->next->next;
		lnk = lnk->next;
	}
	return t1;
}

y u all are creating extra node(p, q, temp etc...)???? it is mention in the question

without creating new node.

y u all are creating extra node(p, q, temp etc...)???? it is mention in the question

without creating new node.

It looks like to me the value are of Binary Search Tree Traversal where b is the root node.
a->b->c->d->e (is actually the In-Order Traversal where b is the root)
and b->a->d->c->e (is the Pre-Order Traversal where b is the root)...

Try putting it in a BST where b is the root...(just look at the letters as ascii value to perform binary insertion and comparison logic...)

Node pairWiseReverse(Node root) {

if (root == null || root.next == null)
return root;

Node back = root;
Node front = root.next;
Node forward = root.next.next;

front.next = back;
back.next = pairWiseReverse(forward);
return front;

}

Node pairWiseReverse(Node root) {

	if (root == null || root.next == null)
		return root;

	Node back = root;
	Node front = root.next;
	Node forward = root.next.next;

	front.next = back;
	back.next = pairWiseReverse(forward);
	return front;

}

swap the value in odd nodes

private void reverseLinkedList(){
int count=0;
LinkListNode temp=head;
while (temp.link!=null){
if(count%2==0){
int x=temp.value;
temp.value=temp.link.value;
temp.link.value=x;

}
temp=temp.link;
count++;
}


}

Complexity - O(N), Space - O(1)

In this question, we need head node of the list.

Step 1: Create a Char pointer.

Step 2: Traverse the list , using head node, and char pointer point info part of the node.

Step 3: Update head=head->next; and swap the value pointed by char pointer and current node value i.e hold by head.

Step 4: Again update char pointer and point to next head node, repeat the above process

static ListNode SwapPairs(ListNode head)
{
if (head == null) return null;
if (head.Next == null) return head;

ListNode ret = head.Next;


while (head != null)
{
ListNode np = head.Next.Next;

head.Next.Next = head;

if (np == null || np.Next == null)
{
head.Next = np;
head = null;
}
else
{

head.Next = np.Next;
head = np;
}
}

return ret;
}

static ListNode SwapPairs(ListNode head)
{
if (head == null) return null;
if (head.Next == null) return head;

ListNode ret = head.Next;


while (head != null)
{
ListNode np = head.Next.Next;

head.Next.Next = head;

if (np == null || np.Next == null)
{
head.Next = np;
head = null;
}
else
{

head.Next = np.Next;
head = np;
}
}

return ret;
}

1. Have two pointers.
2. One pointing to the first element and the other one to the second element.
3. Swap elements that the first and second pointer are pointing to.
4. Repeat step 3 by moving both the pointers two places until anyone pointer points to null.

I am confused isn't it really simple just...

a->next = b->next;
b->next = a

Of course this is not general and only works for the questions stated above.

Here is a way to do it using a counter. Assuming we are provided a Head pointer. It preserves the Head pointer.

public static void awkwardSwap(TreeNode head) {
int count=0;
TreeNode curr = head.next;
TreeNode prev = head;
while(curr!=null) {
   if(count==0) head=curr;
   if(count>=1) prev.next = prev.next.next;
   prev.next = curr.next;
   curr.next - prev;
   curr = prev.next.next;
   prev = prev.next;
   count++;
   }
}

This seems to be pair wise reverse of linked list..
This method will reverse the linked list depending on the given value n.
for n=2 // pair wise reverse.
--------------------------------------------

struct linkedlist* reverse(struct linkedlist *head, int n)  {
	struct linkedlist *temp,*prev,*curr;
	temp = prev = head;
	int count =n;

	while(temp->next  && count>1)
	{
		curr = temp->next;
		temp->next = curr->next;
		curr->next = prev;
		prev = curr;
		count--;
	}
	if(temp->next)
		temp->next = reverse(temp->next, n);
return prev;
}

struct node
{
char data;
struct node* link;
};

struct node * modification(struct node * start ) // start is pointer to start of linked list
{
struct node *p , *q;
char temp;

if(!start || !start-> link)
return;

p = start;
q = start->link;

while (q)
{
temp = p->data;
p->data = q->data;
q->data = temp;
p = q->link;
q = p->link;
}
return start;
}

Here is a working C# code.

public static Link SwapLinks(Link head)
{
    if (head == null || head.Next == null)
        return head;
    Link LastNode = new Link();
    LastNode.Next = head;
    head = head.Next;
    while (LastNode.Next != null && LastNode.Next.Next != null)
    {
        Link trl = LastNode.Next;
        Link fwd = trl.Next;
        LastNode.Next = fwd;
        trl.Next = fwd.Next;
        fwd.Next = trl;
        LastNode = trl;
    }
    return head;
}

Flawless code.... Enjoy!!

#include<iostream>
using namespace std;

typedef struct node
{
	int data;
	node* next;
} node;

void insert(node*& head, int data)
{
	node* t = new node;
	t->data = data;
	t->next = head;
	head = t;
}

void print(node* head)
{
	cout<<endl;
	while(head)
	{
		cout<<head->data<<" ";
		head = head->next;
	}
	cout<<endl;
}

node* revN(node* &head, int n)
{
	if(!head || n < 1)
		return head;

	node* prev = NULL, *cur = head, *next;

	while(cur && n--)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}

	head = prev;
	return next;
}

node* reverseN(node* head, int n)
{
	if(!head || n < 1)
		return head;

	node* newhead = head;
	node* newstart = revN(newhead, n);
	head->next = reverseN(newstart, n);
	return newhead;
}

int main()
{
	node* head = NULL;
	insert(head,5);
	insert(head,4);
	insert(head,3);
	insert(head,2);
	insert(head,1);

	print(head);
	head = reverseN(head,7);
	print(head);

	return 0;
}