/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 方法一 暴力遍历链表放入数组 反向生成新链表
        // if(head == null)
        //     return null;
        // List<Integer> list = new ArrayList<Integer>();
        // ListNode curr = head;
        // while(curr != null) {
        //     list.add(curr.val);
        //     curr = curr.next;
        // }
        // ListNode a = new ListNode(list.get(list.size()-1));
        // ListNode rescurr = a;
        // for(int i = list.size()-2;i>=0;i--) {
        //     rescurr.next = new ListNode(list.get(i));
        //     rescurr = rescurr.next;
        // }
        // rescurr.next = null;
        // return a;
        
        // 方法二 iterative way
        // ListNode prev = null;
        // ListNode curr = head;
        // ListNode next = null;
        // while(curr != null) {
        //     next = curr.next;
        //     curr.next = prev;
        //     prev = curr;
        //     curr = next;
        // }
        // return prev;
        
        // 方法三 recursive way
        if(head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}