version at: 2022-04-04

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
1. 题意:反转单链表
2. 边界: 注意null 与 next null 的情况
3. 思路: 反转当前的结构, 并递归的反转下一层, 在next == null 时停止并保存

*/
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        return reverse(null, head);
    }

    public ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) return prev;

        ListNode next = cur.next;
        cur.next = prev;

        return reverse(cur, next);
    }
}

version at: 2020-02-02

/*
1. 迭代写法:
    1.1 每次翻转指针的指向并将原头结点next赋值为null，返回原来的tail
    1.2 因为指针转向后会丢失原来的next信息，所以要保存p = p2.next,  p2.next = p1 共三个指针
    1.3 因为本题需要保存的是后继节点，所以即使头信息改变也不需要虚拟前置节点了

2. 递归写法, 首先把head.next 翻转好, 然后把head 和 head.next之间的连接翻转, 最后head的next取消即可
*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {    
        // return iteration(head);
        return recursion(head);
    }

    public ListNode recursion(ListNode head){
        if (head == null || head.next == null) return head;
        ListNode p = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    public ListNode iteration(ListNode head){
        if (head == null || head.next == null) return head;
        ListNode p1 = head, p2 = head.next;
        while (p1 != null && p2 != null){
            ListNode p3 = p2.next;
            p2.next = p1;

            p1 = p2;
            p2 = p3;
        }
        head.next = null;
        return p1;
    }

}