CareerCup

public class ListNode<T>
{
private T data;

public T Data
{
get { return data; }
}

private ListNode<T> nextNode;

public ListNode<T> NextNode
{
get { return nextNode; }
set { nextNode = value; }
}

public ListNode(T data)
{
this.data = data;
}

public override string ToString()
{
return data.ToString();
}
}

public class LinkedList<T> where T : class
{
ListNode<T> head = null;

public void Add(T data)
{
ListNode<T> newHead = new ListNode<T>(data);
newHead.NextNode = head;
head = newHead;
}

public void Show()
{
ListNode<T> current = head;
while (current != null)
{
Console.Write(current.Data.ToString() + "; ");
current = current.NextNode;
}
Console.Write(Environment.NewLine);
}

private ListNode<T> PrivateSwapTwo(ListNode<T> current)
{
if ((current != null) && (current.NextNode != null))
{
var tmp1 = current.NextNode.NextNode;
var tmp2 = current.NextNode;
current.NextNode.NextNode = current;
current.NextNode = PrivateSwapTwo(tmp1);

return tmp2;
}
else
{
return current;
}
}


public void SwapTwo()
{
head = PrivateSwapTwo(head);
}
}

/* Program of reverse linked list*/
# include <stdio.h>
# include <malloc.h>

struct node
{
int info;
struct node *link;
}*start;
struct node * rev( struct node * head)
{
struct node * temp = NULL;

if ( head == NULL)
return NULL;
if ( head->link == NULL )
return head;

temp = rev ( head->link );
head->link -> link = head;
head->link = NULL;
return temp;
}

create_list(int num)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info=num;
tmp->link=NULL;

if(start==NULL)
start=tmp;
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}/*End of create_list() */

display()
{
struct node *q;
if(start == NULL)
{
printf("List is empty\n");
return;
}
q=start;
while(q!=NULL)
{
printf("%d ", q->info);
q=q->link;
}
printf("\n");
}/*End of display()*/

reverse()
{
struct node *p1,*p2,*p3;
if(start->link==NULL) /*only one element*/
return;
p1=start;
p2=p1->link;
p3=p2->link;

p1->link=NULL;
p2->link=p1;

while(p3!=NULL)
{
p1=p2;
p2=p3;
p3=p3->link;
p2->link=p1;
}
start=p2;
}/*End of reverse() */
struct node *swaptwo(struct node *head)
{
if((head!=NULL)&&(head->link !=NULL))
{
struct node *tmp1=head->link->link;
struct node *tmp2=head->link;
head->link->link=head;
head->link=swaptwo(tmp1);
return tmp2;


}
else return head;

}
main()
{
int i,n,item;
start=NULL;

printf("How many nodes you want : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the item %d : ",i+1);
scanf("%d",&item);
create_list(item);
}
printf("Initially the linked list is :\n");
display();
start=swaptwo(start);
printf("Linked list after reversing is :\n");
display();
}/*End of main()*/

/*Sachin Gupta MNNIT_ALD

above code is for
1>reverse a linklist
2.revese a linklist using one pointer
3.Swap every consecutive two elements without using value stored in the node of linkedlist

/*Swap every consecutive two elements without using value stored in the node of linkedlist
use*/
struct node *swaptwo(struct node *head)
{
if((head!=NULL)&&(head->link !=NULL))
{
struct node *tmp1=head->link->link;
struct node *tmp2=head->link;
head->link->link=head;
head->link=swaptwo(tmp1);
return tmp2;


}
else return head;

}

@Sachin
Have u even tried running ur code on ur machine ?
It will not do what it is supposed to do and u will even
lose data from the list.
and ur first code is not using single pointer to reverse list
you are taking O(n) space too bcoz of the stack overhead of the RECURSIVE call.
Have u written the code urself or ... ? :P

if you post pseudo code it will be a lot more helpful to understand
btw
nice code

p=head,q=head->next
while(p->next){
temp=q->next
q->next=p
p->next=temp
if(p->next)p=p->next
if(p->next)q=q->next
}

sorry little mistake in abpve code
p=head,q=head->next
while(p->next){
temp=q->next
q->next=p
p->next=temp
if(p->next)p=p->next
if(p->next)q=p->next
}

/* keep 4 pointers - prev, first, second and third. */ 

#include <stdio.h>

struct NODE
{
	int val; 
	NODE* next;
}; 

NODE* CreateLinkedList(int* array, int nElems); 
void PrintLinkedList(NODE* node); 
void ReverseLinkedList(NODE** node); 

int main()
{
	//int array[] = {1,2,3,4,5,6,7}; 
	int array[] = {1,2,3,4,5,6,7,8}; 
	NODE* head; 
	head = CreateLinkedList(array, sizeof(array)/sizeof(array[0])); 
	PrintLinkedList(head); 
	ReverseLinkedList(&head); 
	PrintLinkedList(head); 
	return 0; 
}

NODE* CreateLinkedList(int* array, int nElems) 
{
	NODE* head = NULL; 
	NODE* curr = NULL; 
	NODE* prev = NULL; 

	for( int i = 0; i < nElems; i++ )
	{
		curr = new NODE; 
		curr->val = array[i]; 
		curr->next = NULL; 

		if( prev == NULL )
		{
			head = curr; 
			prev = curr; 
		}
		else
		{
			prev->next = curr; 
			prev = curr; 
		}	
	}
	return head; 
}

void PrintLinkedList(NODE* head)
{
	printf("Linked List is -->\n"); 
	while(head)
	{
		printf("[%d] ", head->val); 
		head = head->next;
	}
	printf("\n"); 
}

void ReverseLinkedList(NODE** head)
{
	NODE* prev = NULL;  
	NODE* first = *head; 
	NODE* second = NULL; 
	NODE* third = NULL; 

	if( first )
		second = first->next; 

	while( first && second )
	{
		third = second->next; 
	
		first->next = third; 
		second->next = first; 

		if( prev == NULL )
			*head = second; 
		else
			prev->next = second; 
		
		prev = first; 

		first = third; 
		if( first )
			second = first->next; 
	}
}

/*Reverse a single linked list using single pointer iteratively and recursively
(Recursive)for iterative code visit sachingupta.tk */
struct list * reverse_ll( struct list * head)
{
struct list * temp = NULL;

if ( head == NULL)
return NULL;
if ( head->next == NULL )
return head;

temp = reverse_ll ( head->next );
head->next -> next = head;
head->next = NULL;
return temp;
}

Here's my 2 cents:

void pairReverse()
{
struct List *a, *b, *c, *prev=NULL;

a = b = c = head;
while(c != NULL && c->next != NULL)
{
if(prev == NULL)
head = head->next;

a = c;
a = a->next;
c = a->next;
a->next = b;
prev = b;
b = c;

if(c != NULL && c->next != NULL)
prev->next = c->next;
else
prev->next = c;
}
}

Please comment on the recursive and iterative version of the problem.

Node RecursiveSwap(Node head){
    if((head == null) || (head->next == null)) return head;
    Node result = head->next;
    head->next = RecursiveSwap(result->next);
    result->next = head;
    return result;
}

Node IterativeSwap(Node head){
 if((head == null) || (head->next == null)) return head;
Node p,q;
p = head;
head = p->next;
while((p != null)&&(p->next != null)){
    q = p->next;
    p->next = q->next;
    p = p->next;
  }
return head;
}

p=head;
q=head->next;
while(q!=NULL)
{
swap(p,q);
p=q->next;
q=q->next->next;
}
swap(node*p,node*q)
{
node*temp=p;
p=q;
q=temp;
}

// We can have a recursive function
swap(node *p)
{
if(p->next==null)
return p;
else
{
q=p->next;
if(q->next!=null)
{
pos=swap(q->next);
q->next=pos;
}
p->next=q->next;
q->next=p;
return q;

}

swap(Node node){
if(node == null) return
prev = null;
while(node != null){
next = node.next.next
node.next.next = node
node.next = next
prev = node
node = next
}
if(prev != null){
temp = node
node = node.next
node.next = temp
}
}

swap(Node node){
if(node == null) return
prev = null;
while(node != null){
next = node.next.next
node.next.next = node
node.next = next
prev = node
node = next
}
if(prev.next != null){
temp = node
node = node.next
node.next = temp
}
}