CareerCup

Solution without recursion, O(n) time and O(1) space

public static Node reverse(Node node) {
        if (node == null)
            return null;

        Node next = node.next;
        node.next = null;

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

void reverseList(struct node * root){
	
	if(root->next==NULL){
		head=root;
		return;
	}
	reverseList(root->next);
	struct node * q=root->next;
		q->next=root;
		root->next=NULL;
	return;
}
int main(){
	
	reverseList(head);

}

void reverseList(struct node * root){
	
	if(root->next==NULL){
		head=root;
		return;
	}
	reverseList(root->next);
	struct node * q=root->next;
		q->next=root;
		root->next=NULL;
	return;
}
int main(){
	reverseList(head);
}

First solution is using stack:

public ListNode reverseWithStack(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ListNode reversed = null;
        ListNode result = null;
        while (!stack.isEmpty()) {
            ListNode current = new ListNode(stack.pop());
            if (reversed == null) {
                reversed = current;
                result = reversed;
            } else {
                reversed.next = current;
                reversed = reversed.next;
            }
        }
        return result;
    }

The second solution doesn't use stack:

public ListNode reverseWithoutStack(ListNode listNode) {
        ListNode result = null;
        while (listNode != null) {
            ListNode curr = new ListNode(listNode.val);
            if (result == null) {
                result = curr;
            } else {
                curr.next = result;
                result = curr;
            }
            listNode = listNode.next;
        }
        return result;
    }

Solution using recursion and iteration both:

class Main {
    static  Node head;
    public static void main(String[] args) {
        Node root = new Node(1);
        Node n1 = new Node(2);
        Node n2 = new Node(3);
        Node n3 = new Node(4);
        Node n4 = new Node(5);
        Node n5 = new Node(6);
        root.next=n1;n1.next=n2;n2.next=n3;n3.next=n4;n4.next=n5;
        printll(root);
        head=root;

        //iterative
        Node currnode = root,prevnode=null,nextnode=null;
        while(currnode!=null){
            nextnode=currnode.next;
            currnode.next=prevnode;
            prevnode=currnode;
            currnode=nextnode;
            head =prevnode;

        }
        printll(head);

        //recursive
        reverse(head);
        printll(head);

    }
    public static void printll(Node root){
        System.out.println("");
        while(root!=null){
            System.out.print(" "+root.data);
            root=root.next;
        }
    }

    public static void reverse(Node root){
        if(root.next==null) {
            head=root;
            return;}
        reverse(root.next);

        Node n = root.next;
        n.next=root;
        root.next=null;
    }
}

class Node{
    int data;
    Node next;

    public Node(int d){
        data=d;
    }
}

foldl (flip (:)) []