Reverse Linked List

Reverse a linked list. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL,

return 5->4->3->2->1->NULL.

Method:

reverse nodes one by one

Solution:

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

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     public int val;
 *     public ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode A) {
        //      1->2->3->4->5->NULL
        //null<-1->2->3->4->5->NULL
        //null<-1<-2->3->4->5->NULL
        ListNode curr = A;
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Solution2:

public ListNode reverseList(ListNode A) {
        //      1->2->3->4->5->NULL
        //      1->2->3->4<-5
        //      1->2<-3<-4<-5
        if (A == null || A.next == null) return A;
        ListNode newHead = reverseList(A.next); // 5
        ListNode curr = A; // 4
        ListNode next = curr.next; //5
        next.next = curr;
        curr.next = null;
        return newHead;
}