Reverse a singly linked list is a simple problem. Iterative and recursive solutions are given below. Note in the recursively solutions we persist a pointer to head.next before calling the function on next node as after reverse the list with head.next as head, head.next will become tail in the partial list. So we can always return new head for the list without losing the pointer to the tail.

Iterasive solution:

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {

ListNode preHead = new ListNode(0); // we need not a stack to save nodes
}
}
}


Recursive solution:

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {