CareerCup

void reverseLinklist(Node **head)
{
Node *ahead=NULL, *curr=NULL, *behind=NULL;
behind=NULL;
curr=*head;
if(curr)
{
ahead=curr->next;

while(ahead)
{
curr->next=behind;
behind = curr;
curr = ahead;
ahead=ahead->next;
}

curr->next=behind;
*head=curr;
}
}

node *reverseList(node *head)
{
node *p1, *p2, *p3;

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

p1=head; p2=head->next;
while (p2)
(
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
)

head -> next = NULL;
head = p1;
return head;
}

void reverseList(node **head)
{
node *result=NULL;
while((*head) != NULL)
{
node *tmp=(*head)->next;
*head->next=result;
result=*head;
*head=tmp;
}
head=*result;
}

main()
{
reverse(head, NULL);
}

void reverse(node* current, node* previous)
{
if(current->next != NULL)
reverse(current->next, current);
current->next = previous;
}

node reverseList(node head) {


node p1, p2;

p1 = p2 = head;

p2 = p2->next;
p1->next = NULL;

while( p2 != null) {


node temp = p2; p2= p2 ->next;

temp->next = p1;
p1 = temp;

}

return p1;
}

I always right it the following way, I think it is more legible

void reverseLinklist(Node **old_list) {
node* new_list = null;
node* element = null;
while (*old_list) {
//Extract top node from old_list
element = *old_list;
*old_list = old_list->next;

//Add to front of new list;
element->next = new_list;
new_list = element;
}
//set old_list to point to correct node (new_list), or return
//new_list depending on function signature
*old_list = new_list;
}

typedef struct MyList MyList;
struct MyList {
int id;
MyList * next;
};

MyList * reverse_list(MyList * list) {

MyList * curNode = NULL, * nextNode = NULL, * tmp = NULL;

curNode = NULL;
nextNode = list;
while(nextNode != NULL) {
tmp = nextNode->next;
nextNode->next = curNode;
curNode = nextNode;
nextNode = tmp;
}

return curNode;
}

Wow! Everyone knows this one.........

how to do it recursively......

hi,how to do it recursively.......

Recursive solution. Let me know if there is something better :

node* reversed_pointer = reverse(head, NULL);

node* reverse(node* curr, node* prev){
  node* temp = curr->next;
  curr->next = prev;
  if(temp == NULL)
    return curr;
  else
    return reverse(temp, curr);
}

reverse(NODE *ptr){
NODE *tmp=head;
while(!head->next){
head=head->next;
reverse(head);
tmp->next->next=tmp;
tmp->next=NULL;
}
}

Node prev = null;
Node cur = root;
while(cur != null)
{
	Node next = cur.Next;
	cur.Next = prev;
	prev = cur;
	cur = next;
}

// prev is new root of the list

Java Code

public static void main(String[] args){
		SLinkedList sl=new SLinkedList();
		sl.insertFirst(1);
		sl.insertFirst(2);
		sl.insertFirst(3);
		sl.insertBefore(4, 2);
		sl.insertAfter(5,4);
		/*sl.reverse();*/
		sl.recursiveReverse(sl.root);		
		
		sl.display();
	}
}

	class Node{
	
		int data;
		Node next;
		public Node(int d){
			this.data=d;
		}
}
	class SLinkedList{
		Node root;
		public SLinkedList(){
			
						
			
		}
		
		
		public void reverse(){
			if(root==null || root.next==null)
				return;			
			else if(root!=null && root.next!=null && root.next.next==null){
				Node curr=root;
				Node next=root.next;
				next.next=curr;
				root=next;
			}
			else{
				Node curr=root;
				Node next=curr.next;
				Node prev=null;
				
				while(curr.next!=null){
					
					next=curr.next;					
					curr.next=prev;
					
					prev=curr;
					curr=next;					
				}
					
				curr.next=prev;
				root=curr;
			}
		}
		
		
		public void recursiveReverse(Node n){
				Node curr=n;
				if(curr==null)
					return;
				
				if(curr.next==null){
					root=curr;
					return;
				}
					
				
				recursiveReverse(n.next);
				
				curr.next.next=curr;
				curr.next=null;
				
								

		}
		
		public void insertFirst(int d){
			Node n=new Node(d);
			if(root==null)
				root=n;
			else{
				n.next=root;
				root=n;
			}
				
		}
		
		public void insertBefore(int v,int d){
			if(root==null)
				return;
			else{
				Node n= new Node(v);
				Node curr=root;
				Node prev=null;
				while(curr.data!=d){
					prev=curr;
					curr=curr.next;
					
					if(curr==null)
						return;
				}
				prev.next=n;
				n.next=curr;
			}
		}
		
		public void insertAfter(int v,int d){
			if(root==null)
				return;
			else{
				Node n=new Node(v);
				Node curr=root;
				Node next=null;
				while(curr.data!=d){
					curr=curr.next;
					next=curr.next;
					
					if(curr==null)
						return;
				}
				
				
				curr.next=n;
				n.next=next;
								
			}
		}
		
		public void remove(int d){
			if(root==null)
				return;
			else{
				Node curr=root;
				Node prev=null;
				while(curr.data!=d){
					prev=curr;
					curr=curr.next;
					
					if(curr==null)
						return;
				}
				
				prev.next=curr.next;
				curr=null;							
				
			}
		}
		
		
		
		
		
		public void display(){
			if(root==null)
				return;
			else{
				Node curr=root;
				while(curr!=null){
					System.out.print(curr.data + " ---> ");
					curr=curr.next;
				}
			}
		}

ListNode* reverse(ListNode *head) {
	ListNode* current, *next, *prev;
	prev=NULL;
	current=head;
	while(current) {
		next=current->next;
		current->next=prev;
		prev=current;
		current=next;
	}
	return prev;
}