CareerCup

Cannot think of an optimal solution for this one. Here it goes, just describing the pseudo code. Think of this problem as if you are asked to reverse the alternate characters in a string (char array)

- Traverse the node in the list
+ Add it to an Array of nodes
- Get the Length of Array
- If Length is odd, Length = Length - 1 //since we start with 0, the last node to be reversed will be even
- for I = 0, J = Length; I <= ArrayLength/2 && J >= ArrayLength/2; I+=2, J-=2)
Swap (I&&J)

- sg December 19, 2008 | Flag Reply

3 variables: current, prev and temp
current is initially pointing to head

while(cur!=null){
temp = cur->next;
cur-next = cur-next-next;
temp->next = cur;
if(cur is not head of the list){
prev->next = temp;
}
prev = cur;
cur = cur->next;
}

- Anonymous January 10, 2009 | Flag Reply

void revalt ( Node *head)
{
struct Node *p, *q, *prev = NULL;
if (head && head->next)
head = p; q= head->next;
head = q;
while (q)
{
struct node *temp = q->next;
q->next = p;
p->next = temp;
if (prev)
prev->next = q;
prev = p;
p= p->next;
if (p)
q= p->next;
else
q = null;
}
}

- Aditya February 17, 2009 | Flag Reply

If extra memory space is allowed to take then just store the reverse link list.Then go for the swapping of alternate positions.

- Anonymous February 23, 2009 | Flag Reply

Can someone further explain this? What does reverse alternate nodes mean?

- JD March 06, 2009 | Flag Reply

If the length of linked list is odd, it is the same as reverse the whole linked list.
I use () to show alternative nodes
e.g. a (b) c (d) e (f) g --reverse--> g f e d c b a, same as reverse the whole list.

If the length of linked list is even, take two elements as a unit, it is same as reverse the linked list units.

e.g. a (b) c (d) e (f) --reverse--> e f c d a b
equivalent (ab)(cd)(ef) -- reverse -->(ef)(cd)(ab)

- Anonymous March 14, 2009 | Flag Reply

while(curr && curr->next) {
tmp = curr->next;
next = tmp ? tmp->next : NULL;

if (tmp) tmp->next = curr;
if (prev) prev->next = tmp;
else head = tmp;

prev = curr;
curr = next;
}
prev ? prev->next = NULL : NULL;
return head;

- Anonymous March 17, 2009 | Flag Reply

while(curr && curr->next) {
tmp = curr->next;
next = tmp ? tmp->next : NULL;

if (tmp) tmp->next = curr;
if (prev) prev->next = tmp;
else head = tmp;

prev = curr;
curr = next;
}
prev ? prev->next = NULL : NULL;
return head;

- DSg March 17, 2009 | Flag Reply

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1206564537

- Erik March 20, 2009 | Flag Reply

node* SwapPairs(node* head)
{
if(!head || !(head->next))
return head;

node* first = head;
node* second = head->next;
node* third = second->next;

second->next=first;
first->next = SwapPairs(third);

return second;
}

- Kiran August 10, 2009 | Flag Reply

@Kiran: Your solution just swaps the nodes next to each other but the question is something else. To get a better idea go through the example of T.

- Natasha August 31, 2009 | Flag Reply

My understanding is if list is:
1-2-3-4-5-6
after reversing it should be:
5-6-3-4-1-2
Is yes, then use 2 stacks, traverse list (s1, s2) and keep putting nodes in alternate stack (s1-> 5-3-1 and s2->6-4-2)and once list is over, build a list by popping nodes from both stack

- Khan November 27, 2009 | Flag Reply

Erik has the perfect solution I think

- Anonymous November 29, 2009 | Flag Reply

There are 3 basic steps as far as i can think
1. Split the main list into 2 lists - each list containing the alternate elements. Each time you add a node to the sublist, do a Push(node). This way the elements in the sublists will be in reverse order
eg: 1-2-3-4-5-6 is split into 2 lists 5-3-1 and 6-4-2
This can be done in O(n) time.

2. Now shuffle merge the 2 sublists, starting from first sublist. This can be done in O(n) time again.
5-6-3-4-1-2

Therefore time complexity is O(n) + O(n) = O(n)

- Aish December 07, 2009 | Flag Reply

Khan is right. Have two stacks. As you traverse the list, push each element in alternate stacks. Then, pop elements from both the stacks & build the resulting list. {{{ Example: 1->2->3->4->5->6. Stack1 will have: -- 5 -- 3 -- 1 -- Stack1 will have: -- 6 -- 4 -- 2 -- }} Now, pop from both stacks (same index-wise) & build the resulting list. So, the result will be: {{{ 5->6->3->4->1->2 }}} If the number of elements in the list is odd, then, dont consider the last node to push to the stack. Complexity: ----------- First traversal of the given list = O(n) Sum of spaces of the two stacks = O(n) To build the resulting list = O(n) or O(1) if we maintain a tail pointer. So, overall complexity comes to O(n). - Helper December 16, 2009 | Flag Reply

i/p: [a] -> b -> [c] -> d -> [e] -> f
alternates nodes are one which are in [] brackets.
o/p: e -> b -> c -> d -> a -> f

my solution:
1) split the list into two different list.
alternate sub list => a->c->e->NULL and normal sub list => b->d->f->NULL
2) reverse alternate sub list. now you have
e->c->a->NULL; and b->d->f->NULL;
3) merge above sub lists node by node to get.
e -> b -> c -> d -> a -> f

all the above steps can be achieved in o(n).

- master December 31, 2009 | Flag Reply

I dont think 2 stacks work. We need 1 stack and 1 queue.
The nodes to be reversed go in the stack.Others go in the queue.
1 -> 2-> 3-> 4 -> 5 -> null
desired result:
5 -> 2 -> 3 -> 4 -> 1-> null
push(1);
enqueue(2);
push(3);
enqueue(4);
push(5);
then:
pop(5);
dequeue(2);
pop(3);
dequeue(4);
pop(1);

running time - O(n)

- Anonymous February 08, 2010 | Flag Reply

void swap(Node* parentQ, Node* Q, Node* parentR, Node* R) {
		if(!parentQ) {
			start = R;
		} else {
			parentQ->next = R;
		}
		if(!parentR) {
			start = Q;
		}else {
			parentR->next = Q;
		}
		Node* temp = Q->next;
		Q->next = R->next;
		R->next = temp;
	}

	void alternateReverse() {
		if(isEmpty()) {
			cout<<"\nEMPTY LIST...";
			return;
		}
		if(!start->next) {
			cout<<"\nONLY ONE ELEMENT IN LIST...";
			return;
		}
		Node *P = NULL, *Q = start, *R = start->next;
		start = R;
		while(R) {
			swap(P,Q,Q,R);
			P = Q;
			Q = Q->next;
			if(!Q)
				return;
			R = Q->next;
		}
	}

- varun October 26, 2013 | Flag Reply