CareerCup

A recursive implementation, call reverseList(head,null) to reverse the list:

public static<T> ListNode<T> reverseList(ListNode<T> head, ListNode<T> prev){
		if (head==null){return prev;}
		
		ListNode<T> temp = head.next();
		head.setNext(prev);
		// the head became the previous element and temp became the new head
		return reverseList(temp,head);
	}

public static LNode reverse(LNode head){
		if(head == null || head.next == null) return head;
		if (head.next.next == null){
			LNode tmp = head.next;
			tmp.next = head;
			head.next = null;
			head = tmp;
			
		}else{
			LNode previus = head;
			LNode current = previus.next;
			LNode next = current.next;
			previus.next = null;
			while(next != null){
				current.next = previus;
				previus = current;
				current = next;
				next = next.next;
	                }

	                current.next = previus;
	                head = current;
		}
		return head;
	}

/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    while (current != NULL)
    {
        next  = current->next;  
        current->next = prev;   
        prev = current;
        current = next;
    }
    *head_ref = prev;
}

void recursiveReverse(struct node** head_ref)
{
    struct node* first;
    struct node* rest;
      
    /* empty list */
    if (*head_ref == NULL)
       return;   
 
    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref;  
    rest  = first->next;
 
    /* List has only one node */
    if (rest == NULL)
       return;   
 
    /* reverse the rest list and put the first element at the end */
    recursiveReverse(&rest);
    first->next->next  = first;  
     
    /* tricky step -- see the diagram */
    first->next  = NULL;          
 
    /* fix the head pointer */
    *head_ref = rest;              
}

public void setNext(ListNode node) {
	this.node = node;
	}
public void getNext() {
	return this.next;
	}

ListNode ReverseList(ListNode head) {
	ListNode temp = null,nextNode = null;
	while(head != null) {
		nextNode = head.getNext();
		head.setNext(temp);
		temp = head;
		head = nextNode;
	}
	return temp;
}

Time complexity:O(n) Space Complexity:O(1)

Given head, reverse rest of list and then add head at the end.

private static Node reverse(Node node) {
        if (node == null || node.next == null) {
            return node;
        }
        Node newHead = reverse(node.next);
        node.next.next = node;
        node.next = null;
        return newHead;
    }